Setting up

First, load the necessary libraries:

library(reticulate) # for R - Python usage
library(grf) # for the regression forest
library(np) # for kernel smoothing methods
library(tidyverse)
library(foreach) # needed for faster implementation of my own NW-estimator
library(doParallel) # needed for faster implementation of my own NW-estimator
library(xgboost)
source("xgboost_smoother.R")

Do the same for Python, the reticulate package usually runs stuff in a particular environment. In order to be safe and have all necessary packages installed, run this code:

virtualenv_create("r-reticulate")
virtualenv: r-reticulate
use_virtualenv("r-reticulate", required = TRUE)
py_config()
python:         /Users/henripfleiderer/.virtualenvs/r-reticulate/bin/python
libpython:      /opt/homebrew/opt/python@3.11/Frameworks/Python.framework/Versions/3.11/lib/python3.11/config-3.11-darwin/libpython3.11.dylib
pythonhome:     /Users/henripfleiderer/.virtualenvs/r-reticulate:/Users/henripfleiderer/.virtualenvs/r-reticulate
version:        3.11.6 (main, Oct  2 2023, 13:45:54) [Clang 15.0.0 (clang-1500.0.40.1)]
numpy:          /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages/numpy
numpy_version:  1.26.4

NOTE: Python version was forced by use_python() function
#use_python("/Users/henripfleiderer/anaconda3/bin/python", required = TRUE)
virtualenv_install(packages = c("numpy==1.26.4","scipy", "scikit-learn","matplotlib","pandas"))
Using virtual environment '~/.virtualenvs/r-reticulate' ...
+ /Users/henripfleiderer/.virtualenvs/r-reticulate/bin/python -m pip install --upgrade --no-user 'numpy==1.26.4' scipy scikit-learn matplotlib pandas
Requirement already satisfied: numpy==1.26.4 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (1.26.4)
Requirement already satisfied: scipy in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (1.13.1)
Requirement already satisfied: scikit-learn in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (1.5.0)
Requirement already satisfied: matplotlib in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (3.9.0)
Requirement already satisfied: pandas in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (2.2.2)
Requirement already satisfied: joblib>=1.2.0 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from scikit-learn) (1.4.0)
Requirement already satisfied: threadpoolctl>=3.1.0 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from scikit-learn) (3.4.0)
Requirement already satisfied: contourpy>=1.0.1 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from matplotlib) (1.2.1)
Requirement already satisfied: cycler>=0.10 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from matplotlib) (0.12.1)
Requirement already satisfied: fonttools>=4.22.0 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from matplotlib) (4.51.0)
Requirement already satisfied: kiwisolver>=1.3.1 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from matplotlib) (1.4.5)
Requirement already satisfied: packaging>=20.0 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from matplotlib) (24.0)
Requirement already satisfied: pillow>=8 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from matplotlib) (10.3.0)
Requirement already satisfied: pyparsing>=2.3.1 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from matplotlib) (3.1.2)
Requirement already satisfied: python-dateutil>=2.7 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from matplotlib) (2.9.0.post0)
Requirement already satisfied: pytz>=2020.1 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from pandas) (2024.1)
Requirement already satisfied: tzdata>=2022.7 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from pandas) (2024.1)
Requirement already satisfied: six>=1.5 in /Users/henripfleiderer/.virtualenvs/r-reticulate/lib/python3.11/site-packages (from python-dateutil>=2.7->matplotlib) (1.16.0)
#py_config()

Now, import the necessary python packages

reticulate::repl_python()
import numpy as np

from sklearn.kernel_ridge import KernelRidge

from sklearn.metrics.pairwise import pairwise_kernels # to manually compute the kernel function

from sklearn.model_selection import GridSearchCV

from scipy import stats

import matplotlib.pyplot as plt

import pandas as pd

from sklearn.gaussian_process.kernels import RBF # matern kernel but for GP 

from sklearn.gaussian_process.kernels import Matern # matern kernel but for GP 

from sklearn.model_selection import RandomizedSearchCV

from scipy.stats import loguniform

from scipy.stats import uniform

Functions for NW smooting in R:

Gaussian kernel, for two input vectors and one bandwidth, common across all dimensions:

quit
gaussian_kernel = function(x1,x2,h, order = 2){
  
  x1 = matrix(x1,ncol = 1)
  x2 = matrix(x2,ncol = 1)
  
  d = dim(x1)[1]
  
  u = sqrt(t(x1-x2)%*%(x1-x2))/h
  
  const = (2*pi)^(1/2)
  
  if(order==2){
  k = exp(-u^2/2)/const
  } else if(order==4){
    k = (3/2 - 1/2*u^2)*exp(-u^2/2)/const
  } else if (order==6){
    k = (15/8 - 5/4*u^2 + 1/8 * u^4)*exp(-u^2/2)/const
  }
  
  return(k)
}

A function for fitting a NW-estimator. With given bandwidth. Uses parallel computing:

fit_kern_Reg_parallel = function(x_test, x_train, y_train, h,...) {
  # Use foreach with .export to ensure functions are available in the parallel environment
  # Use foreach to parallelize the outer loop -> this makes it faster
  n = length(x_train[, 1])
  H_mat = foreach(i = seq_along(x_test[, 1]), .combine = "rbind", .packages = c("base"), .export = c("gaussian_kernel")) %dopar% {
    K_vec = numeric(n)
    
    # Inner loop
    for (j in seq_along(x_train[, 1])) {
      K_vec[j] = gaussian_kernel(x_test[i, ], x_train[j, ], h,...)
    }
    
    # Return row for H_mat
    K_vec / sum(K_vec)
  }
  
  fhat = H_mat%*%y_train
  
  results = list(
    predictions = fhat,
    H = H_mat
  )
  return(results)  # Return predictions
}

A function that computes the Generalized Cross-Validation (GCV) objective, also uses parallel computing. As proposed in Racine (2019):

GCV_kern_smooth_parallel = function(x_train, y_train, h,...) {
  n = length(x_train[, 1])
  
  # Use foreach to parallelize the outer loop -> this makes it faster
  H_mat = foreach(i = seq_along(x_train[, 1]), .combine = "rbind", .packages = c("base"), .export = c("gaussian_kernel")) %dopar% {
    K_vec = numeric(n)
    
    # Inner loop
    for (j in seq_along(x_train[, 1])) {
      K_vec[j] = gaussian_kernel(x_train[i, ], x_train[j, ], h,...)
    }
    
    # Return row for H_mat
    K_vec / sum(K_vec)
  }
  
  # Compute trace and GCV
  trace = sum(diag(diag(n) - H_mat))
  GCV = (trace / n)^(-2) * (1 / n) * sum((y_train - H_mat %*% y_train)^2)
  
  return(GCV)
}

A function that trains the model (optimizes bandwidth) and gives predictions on test points:

fit_kern_Reg_GCV_parallel = function(x_test,x_train,y_train,h_min=0.1,h_max = 2,...){
  # x_eval -> a n_test x d-dimensional matrix of points to evaluate the function:
  # x_train -> training points, x values
  # y_train -> training points, y values
  # h_min -> min value for bandwidth
  # h_max -> max value for bandwidth
  
  # set up parallelization:
  n_cores = detectCores() - 1
  
  # Set up parallel cluster
  cl = makeCluster(n_cores)
  registerDoParallel(cl)
  
  # first, find the optimal bandwidth:
  
  result = optimize(function(h) GCV_kern_smooth_parallel(x_train, y_train, h,...), 
                    interval = c(h_min, h_max), 
                    tol = 1e-3)
  
  # Extract optimal bandwidth
  optimal_h = result$minimum
  
  model_fit = fit_kern_Reg_parallel(x_test,x_train,y_train,optimal_h,...)
  fhat = model_fit$predictions
  optimal_H_mat = model_fit$H
  
  stopCluster(cl)
  result = list(
    predictions = fhat,
    h_opt = optimal_h,
    H_opt = optimal_H_mat
  )
  
  return(result)
}

A function with a jump

Create a multivariate non-smooth function to check the curse of dimensionality.

y_function = function(x){
  y = 0.5*(x>-1&x<2) + 0.5 + 0.1*(x>=2)  #+ cos(-x%*%b)
  return(y)
}

Draw and visualize a realization for \(p = 1\):

set.seed(1234)
p = 1
X = matrix(seq(-5,5,0.01),ncol = 1)
y = y_function(X) + rnorm(dim(X)[1],sd = 0.2)
y_true = y_function(X)
tibble(X,y) %>% 
  ggplot(aes(x = X, y = y)) +
  geom_point(alpha = 0.2)+
  geom_line(aes(x = X, y = y_true), color = "black")+
  theme_minimal()

Fit the function:

Kernel Ridge Regression:

Fit by KRR:

reticulate::repl_python()
param_distributions_Gaussian = {
  "alpha": uniform(1e-9, 1),
  "kernel__length_scale": uniform(1e-9, 1.5),
}

KRR_CV_Gaussian = RandomizedSearchCV(
    KernelRidge(kernel = RBF()),
    param_distributions=param_distributions_Gaussian,
    n_iter=500,
    n_jobs=-1
    )
_ = KRR_CV_Gaussian.fit(r.X,r.y) # fit the kernel ridge regression using cross.validated lambda, suppresses output
#KRR_CV_Gaussian.best_params_
y_hat_KRR_Gaussian = KRR_CV_Gaussian.predict(r.X)
K = RBF(length_scale = KRR_CV_Gaussian.best_params_['kernel__length_scale'],length_scale_bounds = "fixed")
K_mat = K(r.X)
inv = np.linalg.inv(K_mat + KRR_CV_Gaussian.best_params_['alpha']*np.eye(K_mat.shape[0])) 
weight_matrix_Gaussian = K_mat@ inv # weight matrix

Visualize:

quit
y_hat_KRR_Gaussian = as.numeric(py$y_hat_KRR_Gaussian)

tibble(value = c(y_true,y_hat_KRR_Gaussian),
       X_grid = rep(X,2),
       Method = factor(c(rep("True Function", dim(X)[1]),rep("KRR", dim(X)[1])))) %>% 
  ggplot(aes(x = rep(X,2), y = rep(y,2))) +
  geom_point(alpha = 0.2)+
  geom_line(aes(x = X_grid, y = value, color = Method))+
  scale_color_manual(values = c("True Function" = "black", "KRR" = "red")) +
  theme_minimal()

Regression Forest:

reg_forest = regression_forest(X,y, tune.parameters = "all")
y_hat_rf = predict(reg_forest, X)$predictions

tibble(value = c(y_true,y_hat_KRR_Gaussian,y_hat_rf),
       X_grid = rep(X,3),
       Method = factor(c(rep("True Function", dim(X)[1]),rep("KRR", dim(X)[1]), rep("Random Forest", dim(X)[1])))) %>% 
  ggplot(aes(x = rep(X,3), y = rep(y,3))) +
  geom_point(alpha = 0.1)+
  geom_line(aes(x = X_grid, y = value, color = Method))+
  scale_color_manual(values = c("True Function" = "black", "KRR" = "red", "Random Forest" = "green")) +
  theme_minimal()

Nadayara-Watson:

fit_model = fit_kern_Reg_GCV_parallel(X,X,y,0.01,1)
y_hat_np = fit_model$predictions

tibble(value = c(y_true,y_hat_KRR_Gaussian,y_hat_rf,y_hat_np),
       X_grid = rep(X,4),
       Method = factor(c(rep("True Function", dim(X)[1]),rep("KRR", dim(X)[1]), rep("Random Forest", dim(X)[1]), rep("NW", dim(X)[1])    ))) %>% 
  ggplot(aes(x = rep(X,4), y = rep(y,4))) +
  geom_point(alpha = 0.07)+
  geom_line(aes(x = X_grid, y = value, color = Method))+
  scale_color_manual(values = c("True Function" = "black", "KRR" = "red", "Random Forest" = "green", "NW" = "purple")) +
  theme_minimal()+
  labs(x = "x", y = "y")

XG Boost

Set up:

# Convert to DMatrix object
dtrain = xgb.DMatrix(data = as.matrix(X), label = y)
#dtest = xgb.DMatrix(data = as.matrix(test_features), label = test_targets)

# Define model parameters
params = list(
  booster = "gbtree",
  objective = "reg:squarederror",
  eta = 0.85, # Equivalent to learning_rate
  max_depth = 6, # Need to specify a value as XGBoost requires a numerical value
  min_child_weight = 100, # Not a direct equivalent but serves to control over-fitting
  subsample = 1,
  colsample_bytree = 1, # Equivalent to 'sqrt' in max_features
  # Note: XGBoost does not have a direct equivalent for 'max_leaf_nodes' and 'init'
  lambda = 100
)

# Number of boosting rounds (equivalent to n_estimators)
nrounds = 50

# Train the model
model = xgb.train(params = params, data = dtrain, nrounds = nrounds)

Get predictions and smoother matrix:

leaf_indices_train = predict(model, dtrain, predleaf = TRUE)
smoother_train_XG = create_S_from_gbtregressor(model,leaf_indices_train,output_dir,save_output = FALSE)

Plot the prediction:

y_hat_xg=predict(model, dtrain)

tibble(value = c(y_true,y_hat_KRR_Gaussian,y_hat_rf,y_hat_np,y_hat_xg),
       X_grid = rep(X,5),
       Method = factor(c(rep("True Function", dim(X)[1]),rep("KRR", dim(X)[1]), rep("Random Forest", dim(X)[1]), rep("NW", dim(X)[1]) , rep("XGBoost", dim(X)[1])    ))) %>% 
  ggplot(aes(x = rep(X,5), y = rep(y,5))) +
  geom_point(alpha = 0.03)+
  geom_line(aes(x = X_grid, y = value, color = Method))+
  scale_color_manual(values = c("True Function" = "black", "KRR" = "red", "Random Forest" = "green", "NW" = "purple", "XGBoost" = "orange")) +
  theme_minimal()

Equivalent kernels:

Set some points where we want the equivalent kernels:

points = c(-4,-3,-1.05,0.01,1.95,4)
#points = c(-4,-3.5,-2,-1.05,0.01,1.5,1.95,2.5,4)
plot = tibble(X,y) %>% 
  ggplot(aes(x = X, y = y)) +
  geom_point(alpha = 0.2)+
  geom_line(aes(x = X, y = y_true), color = "black")

for (i in 1:length(points)){
  plot = plot+geom_vline(xintercept = points[i], linetype = "dashed")
  
}   
plot + theme_minimal()

Extract the weights

Extract the equivalent kernels/weights applied at these points:

# KRR
results_weights_KRR = matrix(NA,nrow = length(X), ncol = length(points))
colnames(results_weights_KRR) = rep("Temp",length(points))

# Regression Forest
results_weights_RF = matrix(NA,nrow = length(X), ncol = length(points))
colnames(results_weights_RF) = rep("Temp",length(points))

# Nadayara-Watson:
results_weights_NW = matrix(NA,nrow = length(X), ncol = length(points))
colnames(results_weights_NW) = rep("Temp",length(points))

# XG Boost:
results_weights_XG = matrix(NA,nrow = length(X), ncol = length(points))
colnames(results_weights_XG) = rep("Temp",length(points))


weights_KRR_Gaussian = py$weight_matrix_Gaussian



for (i in 1:length(points)){
  # KRR
  results_weights_KRR[,i] = weights_KRR_Gaussian[which(abs((as.numeric(X)-points[i]))<0.000001),]
  colnames(results_weights_KRR)[i] = paste0("x=",points[i])
  # RF:
  results_weights_RF[,i] = matrix(get_forest_weights(reg_forest,as.matrix(points[i])),ncol = 1)
  colnames(results_weights_RF)[i] = paste0("x=",points[i])
    # NW:
  results_weights_NW[,i] = fit_model$H_opt[which(abs((as.numeric(X)-points[i]))<0.000001),]
  colnames(results_weights_NW)[i] = paste0("x=",points[i])
    # XG
  results_weights_XG[,i] = smoother_train_XG[which(abs((as.numeric(X)-points[i]))<0.000001),]
  colnames(results_weights_XG)[i] = paste0("x=",points[i])
  
}
Boundary adaptiveness
points_boundary = c(-4.99,-4.5,-4,-3.5)
#points = c(-4,-3.5,-2,-1.05,0.01,1.5,1.95,2.5,4)
plot = tibble(x = X[1:round(length(y)/2),],y = y[1:round(length(X)/2)]) %>% 
  ggplot(aes(x = x, y = y)) +
  geom_point(alpha = 0.2)+
  geom_line(aes(x = x, y = y_true[1:round(length(X)/2)]), color = "black")

for (i in 1:length(points_boundary)){
  plot = plot+geom_vline(xintercept = points_boundary[i], linetype = "dashed")
  
}   
plot + theme_minimal()

Extract the equivalent kernels/weights applied at these points:

# KRR
results_weights_KRR_boundary = matrix(NA,nrow = length(X), ncol = length(points_boundary))
colnames(results_weights_KRR_boundary) = rep("Temp",length(points_boundary))

# Regression Forest
results_weights_RF_boundary = matrix(NA,nrow = length(X), ncol = length(points_boundary))
colnames(results_weights_RF_boundary) = rep("Temp",length(points_boundary))

# Nadayara-Watson:
results_weights_NW_boundary = matrix(NA,nrow = length(X), ncol = length(points_boundary))
colnames(results_weights_NW_boundary) = rep("Temp",length(points_boundary))

# XGBoost:
results_weights_XG_boundary = matrix(NA,nrow = length(X), ncol = length(points_boundary))
colnames(results_weights_XG_boundary) = rep("Temp",length(points_boundary))


weights_KRR_Gaussian = py$weight_matrix_Gaussian

for (i in 1:length(points_boundary)){
  # KRR
  results_weights_KRR_boundary[,i] = weights_KRR_Gaussian[which(abs((as.numeric(X)-points_boundary[i]))<0.000001),]
  colnames(results_weights_KRR_boundary)[i] = paste0("x=",points_boundary[i])
  # RF:
  results_weights_RF_boundary[,i] = matrix(get_forest_weights(reg_forest,as.matrix(points_boundary[i])),ncol = 1)
  colnames(results_weights_RF_boundary)[i] = paste0("x=",points_boundary[i])
  # NW:
  results_weights_NW_boundary[,i] = fit_model$H_opt[which(abs((as.numeric(X)-points_boundary[i]))<0.000001),]
  colnames(results_weights_NW_boundary)[i] = paste0("x=",points_boundary[i])
  # XG
  results_weights_XG_boundary[,i] = smoother_train_XG[which(abs((as.numeric(X)-points_boundary[i]))<0.000001),]
  colnames(results_weights_XG_boundary)[i] = paste0("x=",points[i])
  
}

Visualize KRR

Visualize for KRR:

results_weights_KRR = as_tibble(results_weights_KRR)
results_weights_KRR = results_weights_KRR %>% mutate(X = as.numeric(X)) %>% pivot_longer(cols = starts_with("x="), names_to = "x", names_prefix = "x=", values_to = "weight") %>% mutate(x = as_factor(x))

results_weights_KRR %>%
  ggplot(aes(x = X, y = weight, color = x))+
  geom_line()+
  theme_minimal()

Boundary

Plot:

results_weights_KRR_boundary = as_tibble(results_weights_KRR_boundary)
results_weights_KRR_boundary = results_weights_KRR_boundary %>% slice_head(n = round(length(y)/2)) %>% mutate(X = as.numeric(X[1:round(length(y)/2),])) %>% pivot_longer(cols = starts_with("x="), names_to = "x", names_prefix = "x=", values_to = "weight") %>% mutate(x = as_factor(x))

results_weights_KRR_boundary %>%
  ggplot(aes(x = X, y = weight, color = x))+
  geom_line()+
  theme_minimal()

Visualize RF

Visualize for regression forest:

results_weights_RF = as_tibble(results_weights_RF)
results_weights_RF = results_weights_RF %>% mutate(X = as.numeric(X)) %>% pivot_longer(cols = starts_with("x="), names_to = "x", names_prefix = "x=", values_to = "weight") %>% mutate(x = as_factor(x))

results_weights_RF %>%
  ggplot(aes(x = X, y = weight, color = x))+
  geom_line()+
  theme_minimal()

Boundary
results_weights_RF_boundary = as_tibble(results_weights_RF_boundary)
results_weights_RF_boundary = results_weights_RF_boundary %>% slice_head(n = round(length(y)/2)) %>% mutate(X = as.numeric(X[1:round(length(y)/2),])) %>% pivot_longer(cols = starts_with("x="), names_to = "x", names_prefix = "x=", values_to = "weight") %>% mutate(x = as_factor(x))

results_weights_RF_boundary %>%
  ggplot(aes(x = X, y = weight, color = x))+
  geom_line()+
  theme_minimal()

Visualize NW:

results_weights_NW = as_tibble(results_weights_NW)
results_weights_NW = results_weights_NW %>% mutate(X = as.numeric(X)) %>% pivot_longer(cols = starts_with("x="), names_to = "x", names_prefix = "x=", values_to = "weight") %>% mutate(x = as_factor(x))

results_weights_NW %>%
  ggplot(aes(x = X, y = weight, color = x))+
  geom_line()+
  theme_minimal()

Boundary
results_weights_NW_boundary = as_tibble(results_weights_NW_boundary)
results_weights_NW_boundary = results_weights_NW_boundary %>% slice_head(n = round(length(y)/2)) %>% mutate(X = as.numeric(X[1:round(length(y)/2),])) %>% pivot_longer(cols = starts_with("x="), names_to = "x", names_prefix = "x=", values_to = "weight") %>% mutate(x = as_factor(x))

results_weights_NW_boundary %>%
  ggplot(aes(x = X, y = weight, color = x))+
  geom_line()+
  theme_minimal()

Visualize XG

results_weights_XG = as_tibble(results_weights_XG)
results_weights_XG = results_weights_XG %>% mutate(X = as.numeric(X)) %>% pivot_longer(cols = starts_with("x="), names_to = "x", names_prefix = "x=", values_to = "weight") %>% mutate(x = as_factor(x))

results_weights_XG %>%
  ggplot(aes(x = X, y = weight, color = x))+
  geom_line()+
  theme_minimal()

Boundary
results_weights_XG_boundary = as_tibble(results_weights_XG_boundary)
results_weights_XG_boundary = results_weights_XG_boundary %>% slice_head(n = round(length(y)/2)) %>% mutate(X = as.numeric(X[1:round(length(y)/2),])) %>% pivot_longer(cols = starts_with("x="), names_to = "x", names_prefix = "x=", values_to = "weight") %>% mutate(x = as_factor(x))

results_weights_XG_boundary %>%
  ggplot(aes(x = X, y = weight, color = x))+
  geom_line()+
  theme_minimal()

New Function, just a line

Create a “simple” function:

y_function = function(x){
  y = 0.5*x
  return(y)
}

Draw and visualize a realization for \(p = 1\). Observations scattered unevenly along the \(x\)-axis:

set.seed(1234)
p = 1
X = matrix(c(runif(500,-5,-2),runif(50,-2,1),runif(1000,1,3),runif(100,3,5)),ncol = 1)
y = y_function(X) + rnorm(dim(X)[1],sd = 0.2)
y_true = y_function(X)
tibble(X,y) %>% 
  ggplot(aes(x = X, y = y)) +
  geom_point(alpha = 0.2)+
  geom_line(aes(x = X, y = y_true), color = "black")+
  theme_minimal()

Fit the function:

Kernel Ridge Regression:

Fit by KRR:

reticulate::repl_python()
param_distributions_Gaussian = {
  "alpha": uniform(1e-9, 1),
  "kernel__length_scale": uniform(1e-9, 1.5),
}

KRR_CV_Gaussian = RandomizedSearchCV(
    KernelRidge(kernel = RBF()),
    param_distributions=param_distributions_Gaussian,
    n_iter=500,
    n_jobs=-1
    )
_ = KRR_CV_Gaussian.fit(r.X,r.y) # fit the kernel ridge regression using cross.validated lambda, suppresses output
#KRR_CV_Gaussian.best_params_
y_hat_KRR_Gaussian = KRR_CV_Gaussian.predict(r.X)
K = RBF(length_scale = KRR_CV_Gaussian.best_params_['kernel__length_scale'],length_scale_bounds = "fixed")
K_mat = K(r.X)
inv = np.linalg.inv(K_mat + KRR_CV_Gaussian.best_params_['alpha']*np.eye(K_mat.shape[0])) 
weight_matrix_Gaussian = K_mat@ inv # weight matrix

Visualize:

quit
y_hat_KRR_Gaussian = as.numeric(py$y_hat_KRR_Gaussian)

tibble(value = c(y_true,y_hat_KRR_Gaussian),
       X_grid = rep(X,2),
       Method = factor(c(rep("True Function", dim(X)[1]),rep("KRR", dim(X)[1])))) %>% 
  ggplot(aes(x = rep(X,2), y = rep(y,2))) +
  geom_point(alpha = 0.2)+
  geom_line(aes(x = X_grid, y = value, color = Method))+
  scale_color_manual(values = c("True Function" = "black", "KRR" = "red")) +
  theme_minimal()

Regression Forest:

reg_forest = regression_forest(X,y, tune.parameters = "all")
y_hat_rf = predict(reg_forest, X)$predictions

tibble(value = c(y_true,y_hat_KRR_Gaussian,y_hat_rf),
       X_grid = rep(X,3),
       Method = factor(c(rep("True Function", dim(X)[1]),rep("KRR", dim(X)[1]), rep("Random Forest", dim(X)[1])))) %>% 
  ggplot(aes(x = rep(X,3), y = rep(y,3))) +
  geom_point(alpha = 0.1)+
  geom_line(aes(x = X_grid, y = value, color = Method))+
  scale_color_manual(values = c("True Function" = "black", "KRR" = "red", "Random Forest" = "green")) +
  theme_minimal()

Nadayara-Watson

fit_model = fit_kern_Reg_GCV_parallel(X,X,y,0.01,1)
y_hat_np = fit_model$predictions

tibble(value = c(y_true,y_hat_KRR_Gaussian,y_hat_rf,y_hat_np),
       X_grid = rep(X,4),
       Method = factor(c(rep("True Function", dim(X)[1]),rep("KRR", dim(X)[1]), rep("Random Forest", dim(X)[1]), rep("NW", dim(X)[1])    ))) %>% 
  ggplot(aes(x = rep(X,4), y = rep(y,4))) +
  geom_point(alpha = 0.07)+
  geom_line(aes(x = X_grid, y = value, color = Method))+
  scale_color_manual(values = c("True Function" = "black", "KRR" = "red", "Random Forest" = "green", "NW" = "purple")) +
  theme_minimal()

XG Boost

Set up:

# Convert to DMatrix object
dtrain = xgb.DMatrix(data = as.matrix(X), label = y)
#dtest = xgb.DMatrix(data = as.matrix(test_features), label = test_targets)

# Define model parameters
params = list(
  booster = "gbtree",
  objective = "reg:squarederror",
  eta = 0.85, # Equivalent to learning_rate
  max_depth = 6, # Need to specify a value as XGBoost requires a numerical value
  min_child_weight = 50, # Not a direct equivalent but serves to control over-fitting
  subsample = 1,
  colsample_bytree = 1, # Equivalent to 'sqrt' in max_features
  # Note: XGBoost does not have a direct equivalent for 'max_leaf_nodes' and 'init'
  lambda = 1
)

# Number of boosting rounds (equivalent to n_estimators)
nrounds = 50

# Train the model
model = xgb.train(params = params, data = dtrain, nrounds = nrounds)

Get predictions and smoother matrix:

leaf_indices_train = predict(model, dtrain, predleaf = TRUE)
smoother_train_XG = create_S_from_gbtregressor(model,leaf_indices_train,output_dir,save_output = FALSE)

Plot the prediction:

y_hat_xg=predict(model, dtrain)

tibble(value = c(y_true,y_hat_KRR_Gaussian,y_hat_rf,y_hat_np,y_hat_xg),
       X_grid = rep(X,5),
       Method = factor(c(rep("True Function", dim(X)[1]),rep("KRR", dim(X)[1]), rep("Random Forest", dim(X)[1]), rep("NW", dim(X)[1]) , rep("XGBoost", dim(X)[1])    ))) %>% 
  ggplot(aes(x = rep(X,5), y = rep(y,5))) +
  geom_point(alpha = 0.03)+
  geom_line(aes(x = X_grid, y = value, color = Method))+
  scale_color_manual(values = c("True Function" = "black", "KRR" = "red", "Random Forest" = "green", "NW" = "purple", "XGBoost" = "orange")) +
  theme_minimal()

Equivalent kernels

Set some points where we want the equivalent kernels:

points = quantile(X,probs = c(0.1,0.2,0.31,0.32,0.35,0.7,0.98), type = 1)
#points = c(-4,-3.5,-2,-1.05,0.01,1.5,1.95,2.5,4)
plot = tibble(X,y) %>% 
  ggplot(aes(x = X, y = y)) +
  geom_point(alpha = 0.2)+
  geom_line(aes(x = X, y = y_true), color = "black")

for (i in 1:length(points)){
  plot = plot+geom_vline(xintercept = points[i], linetype = "dashed")
  
}   
plot + theme_minimal()

Extract the weights:

Extract the equivalent kernels/weights applied at these points:

# KRR
results_weights_KRR = matrix(NA,nrow = length(X), ncol = length(points))
colnames(results_weights_KRR) = rep("Temp",length(points))

# Regression Forest
results_weights_RF = matrix(NA,nrow = length(X), ncol = length(points))
colnames(results_weights_RF) = rep("Temp",length(points))

# Nadayara-Watson:
results_weights_NW = matrix(NA,nrow = length(X), ncol = length(points))
colnames(results_weights_NW) = rep("Temp",length(points))

# XG Boost:
results_weights_XG = matrix(NA,nrow = length(X), ncol = length(points))
colnames(results_weights_XG) = rep("Temp",length(points))

weights_KRR_Gaussian = py$weight_matrix_Gaussian

for (i in 1:length(points)){
  # KRR
  results_weights_KRR[,i] = weights_KRR_Gaussian[which(abs((as.numeric(X)-points[i]))<0.000001),]
  colnames(results_weights_KRR)[i] = paste0("x=",points[i])
  # RF:
  results_weights_RF[,i] = matrix(get_forest_weights(reg_forest,as.matrix(points[i])),ncol = 1)
  colnames(results_weights_RF)[i] = paste0("x=",points[i])
  # NW:
  results_weights_NW[,i] = fit_model$H_opt[which(abs((as.numeric(X)-points[i]))<0.000001),]
  colnames(results_weights_NW)[i] = paste0("x=",points[i])
  # XG
  results_weights_XG[,i] = smoother_train_XG[which(abs((as.numeric(X)-points[i]))<0.000001),]
  colnames(results_weights_XG)[i] = paste0("x=",points[i])
  
}

Visualize KRR

Visualize for KRR:

results_weights_KRR = as_tibble(results_weights_KRR)
results_weights_KRR = results_weights_KRR %>% mutate(X = as.numeric(X)) %>% pivot_longer(cols = starts_with("x="), names_to = "x", names_prefix = "x=", values_to = "weight") %>% mutate(x = as_factor(x))

results_weights_KRR %>%
  ggplot(aes(x = X, y = weight, color = x))+
  geom_line()+
  theme_minimal()

Visualize RF

Visualize for KRR:

results_weights_RF = as_tibble(results_weights_RF)
results_weights_RF = results_weights_RF %>% mutate(X = as.numeric(X)) %>% pivot_longer(cols = starts_with("x="), names_to = "x", names_prefix = "x=", values_to = "weight") %>% mutate(x = as_factor(x))

results_weights_RF %>%
  ggplot(aes(x = X, y = weight, color = x))+
  geom_line()+
  theme_minimal()

Visualize NW

results_weights_NW = as_tibble(results_weights_NW)
results_weights_NW = results_weights_NW %>% mutate(X = as.numeric(X)) %>% pivot_longer(cols = starts_with("x="), names_to = "x", names_prefix = "x=", values_to = "weight") %>% mutate(x = as_factor(x))

results_weights_NW %>%
  ggplot(aes(x = X, y = weight, color = x))+
  geom_line()+
  theme_minimal()

Visualize XG

results_weights_XG = as_tibble(results_weights_XG)
results_weights_XG = results_weights_XG %>% mutate(X = as.numeric(X)) %>% pivot_longer(cols = starts_with("x="), names_to = "x", names_prefix = "x=", values_to = "weight") %>% mutate(x = as_factor(x))

results_weights_XG %>%
  ggplot(aes(x = X, y = weight, color = x))+
  geom_line()+
  theme_minimal()

References

Racine, Jeffrey S. 2019. An Introduction to the Advanced Theory and Practice of Nonparametric Econometrics: A Replicable Approach Using R. Cambridge: Cambridge University Press. https://doi.org/10.1017/9781108649841.
LS0tCnRpdGxlOiAiRXF1aXZhbGVudCBLZXJuZWwgLSBmdW5jdGlvbiB3aXRoIGp1bXBzL2N1dC1vZmYgcG9pbnRzIgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKYmlibGlvZ3JhcGh5OiByZWZlcmVuY2VzLmJpYgotLS0KCiMgU2V0dGluZyB1cAoKRmlyc3QsIGxvYWQgdGhlIG5lY2Vzc2FyeSBsaWJyYXJpZXM6CgpgYGB7ciBwYWNrYWdlcyx3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2U9RkFMU0UsIHJlc3VsdHMgPSAnaGlkZSd9CmxpYnJhcnkocmV0aWN1bGF0ZSkgIyBmb3IgUiAtIFB5dGhvbiB1c2FnZQpsaWJyYXJ5KGdyZikgIyBmb3IgdGhlIHJlZ3Jlc3Npb24gZm9yZXN0CmxpYnJhcnkobnApICMgZm9yIGtlcm5lbCBzbW9vdGhpbmcgbWV0aG9kcwpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShmb3JlYWNoKSAjIG5lZWRlZCBmb3IgZmFzdGVyIGltcGxlbWVudGF0aW9uIG9mIG15IG93biBOVy1lc3RpbWF0b3IKbGlicmFyeShkb1BhcmFsbGVsKSAjIG5lZWRlZCBmb3IgZmFzdGVyIGltcGxlbWVudGF0aW9uIG9mIG15IG93biBOVy1lc3RpbWF0b3IKbGlicmFyeSh4Z2Jvb3N0KQpzb3VyY2UoInhnYm9vc3Rfc21vb3RoZXIuUiIpCmBgYAoKRG8gdGhlIHNhbWUgZm9yIFB5dGhvbiwgdGhlIHJldGljdWxhdGUgcGFja2FnZSB1c3VhbGx5IHJ1bnMgc3R1ZmYgaW4gYSBwYXJ0aWN1bGFyIGVudmlyb25tZW50LiBJbiBvcmRlciB0byBiZSBzYWZlIGFuZCBoYXZlIGFsbCBuZWNlc3NhcnkgcGFja2FnZXMgaW5zdGFsbGVkLCBydW4gdGhpcyBjb2RlOgoKCmBgYHtyLCBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmc9RkFMU0V9CnZpcnR1YWxlbnZfY3JlYXRlKCJyLXJldGljdWxhdGUiKQp1c2VfdmlydHVhbGVudigici1yZXRpY3VsYXRlIiwgcmVxdWlyZWQgPSBUUlVFKQpweV9jb25maWcoKQojdXNlX3B5dGhvbigiL1VzZXJzL2hlbnJpcGZsZWlkZXJlci9hbmFjb25kYTMvYmluL3B5dGhvbiIsIHJlcXVpcmVkID0gVFJVRSkKdmlydHVhbGVudl9pbnN0YWxsKHBhY2thZ2VzID0gYygibnVtcHk9PTEuMjYuNCIsInNjaXB5IiwgInNjaWtpdC1sZWFybiIsIm1hdHBsb3RsaWIiLCJwYW5kYXMiKSkKI3B5X2NvbmZpZygpCmBgYAoKTm93LCBpbXBvcnQgdGhlIG5lY2Vzc2FyeSBweXRob24gcGFja2FnZXMgCmBgYHtweXRob259CmltcG9ydCBudW1weSBhcyBucAoKZnJvbSBza2xlYXJuLmtlcm5lbF9yaWRnZSBpbXBvcnQgS2VybmVsUmlkZ2UKCmZyb20gc2tsZWFybi5tZXRyaWNzLnBhaXJ3aXNlIGltcG9ydCBwYWlyd2lzZV9rZXJuZWxzICMgdG8gbWFudWFsbHkgY29tcHV0ZSB0aGUga2VybmVsIGZ1bmN0aW9uCgpmcm9tIHNrbGVhcm4ubW9kZWxfc2VsZWN0aW9uIGltcG9ydCBHcmlkU2VhcmNoQ1YKCmZyb20gc2NpcHkgaW1wb3J0IHN0YXRzCgppbXBvcnQgbWF0cGxvdGxpYi5weXBsb3QgYXMgcGx0CgppbXBvcnQgcGFuZGFzIGFzIHBkCgpmcm9tIHNrbGVhcm4uZ2F1c3NpYW5fcHJvY2Vzcy5rZXJuZWxzIGltcG9ydCBSQkYgIyBtYXRlcm4ga2VybmVsIGJ1dCBmb3IgR1AgCgpmcm9tIHNrbGVhcm4uZ2F1c3NpYW5fcHJvY2Vzcy5rZXJuZWxzIGltcG9ydCBNYXRlcm4gIyBtYXRlcm4ga2VybmVsIGJ1dCBmb3IgR1AgCgpmcm9tIHNrbGVhcm4ubW9kZWxfc2VsZWN0aW9uIGltcG9ydCBSYW5kb21pemVkU2VhcmNoQ1YKCmZyb20gc2NpcHkuc3RhdHMgaW1wb3J0IGxvZ3VuaWZvcm0KCmZyb20gc2NpcHkuc3RhdHMgaW1wb3J0IHVuaWZvcm0KYGBgCgojIEZ1bmN0aW9ucyBmb3IgTlcgc21vb3RpbmcgaW4gUjoKCkdhdXNzaWFuIGtlcm5lbCwgZm9yIHR3byBpbnB1dCB2ZWN0b3JzIGFuZCBvbmUgYmFuZHdpZHRoLCBjb21tb24gYWNyb3NzIGFsbCBkaW1lbnNpb25zOgpgYGB7cn0KZ2F1c3NpYW5fa2VybmVsID0gZnVuY3Rpb24oeDEseDIsaCwgb3JkZXIgPSAyKXsKICAKICB4MSA9IG1hdHJpeCh4MSxuY29sID0gMSkKICB4MiA9IG1hdHJpeCh4MixuY29sID0gMSkKICAKICBkID0gZGltKHgxKVsxXQogIAogIHUgPSBzcXJ0KHQoeDEteDIpJSolKHgxLXgyKSkvaAogIAogIGNvbnN0ID0gKDIqcGkpXigxLzIpCiAgCiAgaWYob3JkZXI9PTIpewogIGsgPSBleHAoLXVeMi8yKS9jb25zdAogIH0gZWxzZSBpZihvcmRlcj09NCl7CiAgICBrID0gKDMvMiAtIDEvMip1XjIpKmV4cCgtdV4yLzIpL2NvbnN0CiAgfSBlbHNlIGlmIChvcmRlcj09Nil7CiAgICBrID0gKDE1LzggLSA1LzQqdV4yICsgMS84ICogdV40KSpleHAoLXVeMi8yKS9jb25zdAogIH0KICAKICByZXR1cm4oaykKfQpgYGAKCkEgZnVuY3Rpb24gZm9yIGZpdHRpbmcgYSBOVy1lc3RpbWF0b3IuIFdpdGggZ2l2ZW4gYmFuZHdpZHRoLiBVc2VzIHBhcmFsbGVsIGNvbXB1dGluZzoKCmBgYHtyfQpmaXRfa2Vybl9SZWdfcGFyYWxsZWwgPSBmdW5jdGlvbih4X3Rlc3QsIHhfdHJhaW4sIHlfdHJhaW4sIGgsLi4uKSB7CiAgIyBVc2UgZm9yZWFjaCB3aXRoIC5leHBvcnQgdG8gZW5zdXJlIGZ1bmN0aW9ucyBhcmUgYXZhaWxhYmxlIGluIHRoZSBwYXJhbGxlbCBlbnZpcm9ubWVudAogICMgVXNlIGZvcmVhY2ggdG8gcGFyYWxsZWxpemUgdGhlIG91dGVyIGxvb3AgLT4gdGhpcyBtYWtlcyBpdCBmYXN0ZXIKICBuID0gbGVuZ3RoKHhfdHJhaW5bLCAxXSkKICBIX21hdCA9IGZvcmVhY2goaSA9IHNlcV9hbG9uZyh4X3Rlc3RbLCAxXSksIC5jb21iaW5lID0gInJiaW5kIiwgLnBhY2thZ2VzID0gYygiYmFzZSIpLCAuZXhwb3J0ID0gYygiZ2F1c3NpYW5fa2VybmVsIikpICVkb3BhciUgewogICAgS192ZWMgPSBudW1lcmljKG4pCiAgICAKICAgICMgSW5uZXIgbG9vcAogICAgZm9yIChqIGluIHNlcV9hbG9uZyh4X3RyYWluWywgMV0pKSB7CiAgICAgIEtfdmVjW2pdID0gZ2F1c3NpYW5fa2VybmVsKHhfdGVzdFtpLCBdLCB4X3RyYWluW2osIF0sIGgsLi4uKQogICAgfQogICAgCiAgICAjIFJldHVybiByb3cgZm9yIEhfbWF0CiAgICBLX3ZlYyAvIHN1bShLX3ZlYykKICB9CiAgCiAgZmhhdCA9IEhfbWF0JSoleV90cmFpbgogIAogIHJlc3VsdHMgPSBsaXN0KAogICAgcHJlZGljdGlvbnMgPSBmaGF0LAogICAgSCA9IEhfbWF0CiAgKQogIHJldHVybihyZXN1bHRzKSAgIyBSZXR1cm4gcHJlZGljdGlvbnMKfQoKYGBgCgpBIGZ1bmN0aW9uIHRoYXQgY29tcHV0ZXMgdGhlIEdlbmVyYWxpemVkIENyb3NzLVZhbGlkYXRpb24gKEdDVikgb2JqZWN0aXZlLCBhbHNvIHVzZXMgcGFyYWxsZWwgY29tcHV0aW5nLiBBcyBwcm9wb3NlZCBpbiBAcmFjaW5lX2ludHJvZHVjdGlvbl8yMDE5OgoKYGBge3J9CkdDVl9rZXJuX3Ntb290aF9wYXJhbGxlbCA9IGZ1bmN0aW9uKHhfdHJhaW4sIHlfdHJhaW4sIGgsLi4uKSB7CiAgbiA9IGxlbmd0aCh4X3RyYWluWywgMV0pCiAgCiAgIyBVc2UgZm9yZWFjaCB0byBwYXJhbGxlbGl6ZSB0aGUgb3V0ZXIgbG9vcCAtPiB0aGlzIG1ha2VzIGl0IGZhc3RlcgogIEhfbWF0ID0gZm9yZWFjaChpID0gc2VxX2Fsb25nKHhfdHJhaW5bLCAxXSksIC5jb21iaW5lID0gInJiaW5kIiwgLnBhY2thZ2VzID0gYygiYmFzZSIpLCAuZXhwb3J0ID0gYygiZ2F1c3NpYW5fa2VybmVsIikpICVkb3BhciUgewogICAgS192ZWMgPSBudW1lcmljKG4pCiAgICAKICAgICMgSW5uZXIgbG9vcAogICAgZm9yIChqIGluIHNlcV9hbG9uZyh4X3RyYWluWywgMV0pKSB7CiAgICAgIEtfdmVjW2pdID0gZ2F1c3NpYW5fa2VybmVsKHhfdHJhaW5baSwgXSwgeF90cmFpbltqLCBdLCBoLC4uLikKICAgIH0KICAgIAogICAgIyBSZXR1cm4gcm93IGZvciBIX21hdAogICAgS192ZWMgLyBzdW0oS192ZWMpCiAgfQogIAogICMgQ29tcHV0ZSB0cmFjZSBhbmQgR0NWCiAgdHJhY2UgPSBzdW0oZGlhZyhkaWFnKG4pIC0gSF9tYXQpKQogIEdDViA9ICh0cmFjZSAvIG4pXigtMikgKiAoMSAvIG4pICogc3VtKCh5X3RyYWluIC0gSF9tYXQgJSolIHlfdHJhaW4pXjIpCiAgCiAgcmV0dXJuKEdDVikKfQpgYGAKCkEgZnVuY3Rpb24gdGhhdCB0cmFpbnMgdGhlIG1vZGVsIChvcHRpbWl6ZXMgYmFuZHdpZHRoKSBhbmQgZ2l2ZXMgcHJlZGljdGlvbnMgb24gdGVzdCBwb2ludHM6CmBgYHtyfQpmaXRfa2Vybl9SZWdfR0NWX3BhcmFsbGVsID0gZnVuY3Rpb24oeF90ZXN0LHhfdHJhaW4seV90cmFpbixoX21pbj0wLjEsaF9tYXggPSAyLC4uLil7CiAgIyB4X2V2YWwgLT4gYSBuX3Rlc3QgeCBkLWRpbWVuc2lvbmFsIG1hdHJpeCBvZiBwb2ludHMgdG8gZXZhbHVhdGUgdGhlIGZ1bmN0aW9uOgogICMgeF90cmFpbiAtPiB0cmFpbmluZyBwb2ludHMsIHggdmFsdWVzCiAgIyB5X3RyYWluIC0+IHRyYWluaW5nIHBvaW50cywgeSB2YWx1ZXMKICAjIGhfbWluIC0+IG1pbiB2YWx1ZSBmb3IgYmFuZHdpZHRoCiAgIyBoX21heCAtPiBtYXggdmFsdWUgZm9yIGJhbmR3aWR0aAogIAogICMgc2V0IHVwIHBhcmFsbGVsaXphdGlvbjoKICBuX2NvcmVzID0gZGV0ZWN0Q29yZXMoKSAtIDEKICAKICAjIFNldCB1cCBwYXJhbGxlbCBjbHVzdGVyCiAgY2wgPSBtYWtlQ2x1c3RlcihuX2NvcmVzKQogIHJlZ2lzdGVyRG9QYXJhbGxlbChjbCkKICAKICAjIGZpcnN0LCBmaW5kIHRoZSBvcHRpbWFsIGJhbmR3aWR0aDoKICAKICByZXN1bHQgPSBvcHRpbWl6ZShmdW5jdGlvbihoKSBHQ1Zfa2Vybl9zbW9vdGhfcGFyYWxsZWwoeF90cmFpbiwgeV90cmFpbiwgaCwuLi4pLCAKICAgICAgICAgICAgICAgICAgICBpbnRlcnZhbCA9IGMoaF9taW4sIGhfbWF4KSwgCiAgICAgICAgICAgICAgICAgICAgdG9sID0gMWUtMykKICAKICAjIEV4dHJhY3Qgb3B0aW1hbCBiYW5kd2lkdGgKICBvcHRpbWFsX2ggPSByZXN1bHQkbWluaW11bQogIAogIG1vZGVsX2ZpdCA9IGZpdF9rZXJuX1JlZ19wYXJhbGxlbCh4X3Rlc3QseF90cmFpbix5X3RyYWluLG9wdGltYWxfaCwuLi4pCiAgZmhhdCA9IG1vZGVsX2ZpdCRwcmVkaWN0aW9ucwogIG9wdGltYWxfSF9tYXQgPSBtb2RlbF9maXQkSAogIAogIHN0b3BDbHVzdGVyKGNsKQogIHJlc3VsdCA9IGxpc3QoCiAgICBwcmVkaWN0aW9ucyA9IGZoYXQsCiAgICBoX29wdCA9IG9wdGltYWxfaCwKICAgIEhfb3B0ID0gb3B0aW1hbF9IX21hdAogICkKICAKICByZXR1cm4ocmVzdWx0KQp9CgpgYGAKCiMgQSBmdW5jdGlvbiB3aXRoIGEganVtcCAKCkNyZWF0ZSBhIG11bHRpdmFyaWF0ZSBub24tc21vb3RoIGZ1bmN0aW9uIHRvIGNoZWNrIHRoZSBjdXJzZSBvZiBkaW1lbnNpb25hbGl0eS4KCmBgYHtyfQp5X2Z1bmN0aW9uID0gZnVuY3Rpb24oeCl7CiAgeSA9IDAuNSooeD4tMSZ4PDIpICsgMC41ICsgMC4xKih4Pj0yKSAgIysgY29zKC14JSolYikKICByZXR1cm4oeSkKfQpgYGAKCkRyYXcgYW5kIHZpc3VhbGl6ZSBhIHJlYWxpemF0aW9uIGZvciAkcCA9IDEkOgoKYGBge3J9CnNldC5zZWVkKDEyMzQpCnAgPSAxClggPSBtYXRyaXgoc2VxKC01LDUsMC4wMSksbmNvbCA9IDEpCnkgPSB5X2Z1bmN0aW9uKFgpICsgcm5vcm0oZGltKFgpWzFdLHNkID0gMC4yKQp5X3RydWUgPSB5X2Z1bmN0aW9uKFgpCnRpYmJsZShYLHkpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSBYLCB5ID0geSkpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC4yKSsKICBnZW9tX2xpbmUoYWVzKHggPSBYLCB5ID0geV90cnVlKSwgY29sb3IgPSAiYmxhY2siKSsKICB0aGVtZV9taW5pbWFsKCkKYGBgCiMgRml0IHRoZSBmdW5jdGlvbjoKCiMjIyBLZXJuZWwgUmlkZ2UgUmVncmVzc2lvbjoKCkZpdCBieSBLUlI6CgoKYGBge3B5dGhvbn0KcGFyYW1fZGlzdHJpYnV0aW9uc19HYXVzc2lhbiA9IHsKICAiYWxwaGEiOiB1bmlmb3JtKDFlLTksIDEpLAogICJrZXJuZWxfX2xlbmd0aF9zY2FsZSI6IHVuaWZvcm0oMWUtOSwgMS41KSwKfQoKS1JSX0NWX0dhdXNzaWFuID0gUmFuZG9taXplZFNlYXJjaENWKAogICAgS2VybmVsUmlkZ2Uoa2VybmVsID0gUkJGKCkpLAogICAgcGFyYW1fZGlzdHJpYnV0aW9ucz1wYXJhbV9kaXN0cmlidXRpb25zX0dhdXNzaWFuLAogICAgbl9pdGVyPTUwMCwKICAgIG5fam9icz0tMQogICAgKQpfID0gS1JSX0NWX0dhdXNzaWFuLmZpdChyLlgsci55KSAjIGZpdCB0aGUga2VybmVsIHJpZGdlIHJlZ3Jlc3Npb24gdXNpbmcgY3Jvc3MudmFsaWRhdGVkIGxhbWJkYSwgc3VwcHJlc3NlcyBvdXRwdXQKI0tSUl9DVl9HYXVzc2lhbi5iZXN0X3BhcmFtc18KeV9oYXRfS1JSX0dhdXNzaWFuID0gS1JSX0NWX0dhdXNzaWFuLnByZWRpY3Qoci5YKQpLID0gUkJGKGxlbmd0aF9zY2FsZSA9IEtSUl9DVl9HYXVzc2lhbi5iZXN0X3BhcmFtc19bJ2tlcm5lbF9fbGVuZ3RoX3NjYWxlJ10sbGVuZ3RoX3NjYWxlX2JvdW5kcyA9ICJmaXhlZCIpCktfbWF0ID0gSyhyLlgpCmludiA9IG5wLmxpbmFsZy5pbnYoS19tYXQgKyBLUlJfQ1ZfR2F1c3NpYW4uYmVzdF9wYXJhbXNfWydhbHBoYSddKm5wLmV5ZShLX21hdC5zaGFwZVswXSkpIAp3ZWlnaHRfbWF0cml4X0dhdXNzaWFuID0gS19tYXRAIGludiAjIHdlaWdodCBtYXRyaXgKYGBgCgpWaXN1YWxpemU6CgpgYGB7cn0KeV9oYXRfS1JSX0dhdXNzaWFuID0gYXMubnVtZXJpYyhweSR5X2hhdF9LUlJfR2F1c3NpYW4pCgp0aWJibGUodmFsdWUgPSBjKHlfdHJ1ZSx5X2hhdF9LUlJfR2F1c3NpYW4pLAogICAgICAgWF9ncmlkID0gcmVwKFgsMiksCiAgICAgICBNZXRob2QgPSBmYWN0b3IoYyhyZXAoIlRydWUgRnVuY3Rpb24iLCBkaW0oWClbMV0pLHJlcCgiS1JSIiwgZGltKFgpWzFdKSkpKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gcmVwKFgsMiksIHkgPSByZXAoeSwyKSkpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC4yKSsKICBnZW9tX2xpbmUoYWVzKHggPSBYX2dyaWQsIHkgPSB2YWx1ZSwgY29sb3IgPSBNZXRob2QpKSsKICBzY2FsZV9jb2xvcl9tYW51YWwodmFsdWVzID0gYygiVHJ1ZSBGdW5jdGlvbiIgPSAiYmxhY2siLCAiS1JSIiA9ICJyZWQiKSkgKwogIHRoZW1lX21pbmltYWwoKQpgYGAKCiMjIyBSZWdyZXNzaW9uIEZvcmVzdDoKCmBgYHtyfQpyZWdfZm9yZXN0ID0gcmVncmVzc2lvbl9mb3Jlc3QoWCx5LCB0dW5lLnBhcmFtZXRlcnMgPSAiYWxsIikKeV9oYXRfcmYgPSBwcmVkaWN0KHJlZ19mb3Jlc3QsIFgpJHByZWRpY3Rpb25zCgp0aWJibGUodmFsdWUgPSBjKHlfdHJ1ZSx5X2hhdF9LUlJfR2F1c3NpYW4seV9oYXRfcmYpLAogICAgICAgWF9ncmlkID0gcmVwKFgsMyksCiAgICAgICBNZXRob2QgPSBmYWN0b3IoYyhyZXAoIlRydWUgRnVuY3Rpb24iLCBkaW0oWClbMV0pLHJlcCgiS1JSIiwgZGltKFgpWzFdKSwgcmVwKCJSYW5kb20gRm9yZXN0IiwgZGltKFgpWzFdKSkpKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gcmVwKFgsMyksIHkgPSByZXAoeSwzKSkpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC4xKSsKICBnZW9tX2xpbmUoYWVzKHggPSBYX2dyaWQsIHkgPSB2YWx1ZSwgY29sb3IgPSBNZXRob2QpKSsKICBzY2FsZV9jb2xvcl9tYW51YWwodmFsdWVzID0gYygiVHJ1ZSBGdW5jdGlvbiIgPSAiYmxhY2siLCAiS1JSIiA9ICJyZWQiLCAiUmFuZG9tIEZvcmVzdCIgPSAiZ3JlZW4iKSkgKwogIHRoZW1lX21pbmltYWwoKQpgYGAKCiMjIyBOYWRheWFyYS1XYXRzb246CmBgYHtyfQpmaXRfbW9kZWwgPSBmaXRfa2Vybl9SZWdfR0NWX3BhcmFsbGVsKFgsWCx5LDAuMDEsMSkKeV9oYXRfbnAgPSBmaXRfbW9kZWwkcHJlZGljdGlvbnMKCnRpYmJsZSh2YWx1ZSA9IGMoeV90cnVlLHlfaGF0X0tSUl9HYXVzc2lhbix5X2hhdF9yZix5X2hhdF9ucCksCiAgICAgICBYX2dyaWQgPSByZXAoWCw0KSwKICAgICAgIE1ldGhvZCA9IGZhY3RvcihjKHJlcCgiVHJ1ZSBGdW5jdGlvbiIsIGRpbShYKVsxXSkscmVwKCJLUlIiLCBkaW0oWClbMV0pLCByZXAoIlJhbmRvbSBGb3Jlc3QiLCBkaW0oWClbMV0pLCByZXAoIk5XIiwgZGltKFgpWzFdKSAgICApKSkgJT4lIAogIGdncGxvdChhZXMoeCA9IHJlcChYLDQpLCB5ID0gcmVwKHksNCkpKSArCiAgZ2VvbV9wb2ludChhbHBoYSA9IDAuMDcpKwogIGdlb21fbGluZShhZXMoeCA9IFhfZ3JpZCwgeSA9IHZhbHVlLCBjb2xvciA9IE1ldGhvZCkpKwogIHNjYWxlX2NvbG9yX21hbnVhbCh2YWx1ZXMgPSBjKCJUcnVlIEZ1bmN0aW9uIiA9ICJibGFjayIsICJLUlIiID0gInJlZCIsICJSYW5kb20gRm9yZXN0IiA9ICJncmVlbiIsICJOVyIgPSAicHVycGxlIikpICsKICB0aGVtZV9taW5pbWFsKCkrCiAgbGFicyh4ID0gIngiLCB5ID0gInkiKQpgYGAKCiMjIyBYRyBCb29zdAoKU2V0IHVwOgoKYGBge3J9CiMgQ29udmVydCB0byBETWF0cml4IG9iamVjdApkdHJhaW4gPSB4Z2IuRE1hdHJpeChkYXRhID0gYXMubWF0cml4KFgpLCBsYWJlbCA9IHkpCiNkdGVzdCA9IHhnYi5ETWF0cml4KGRhdGEgPSBhcy5tYXRyaXgodGVzdF9mZWF0dXJlcyksIGxhYmVsID0gdGVzdF90YXJnZXRzKQoKIyBEZWZpbmUgbW9kZWwgcGFyYW1ldGVycwpwYXJhbXMgPSBsaXN0KAogIGJvb3N0ZXIgPSAiZ2J0cmVlIiwKICBvYmplY3RpdmUgPSAicmVnOnNxdWFyZWRlcnJvciIsCiAgZXRhID0gMC44NSwgIyBFcXVpdmFsZW50IHRvIGxlYXJuaW5nX3JhdGUKICBtYXhfZGVwdGggPSA2LCAjIE5lZWQgdG8gc3BlY2lmeSBhIHZhbHVlIGFzIFhHQm9vc3QgcmVxdWlyZXMgYSBudW1lcmljYWwgdmFsdWUKICBtaW5fY2hpbGRfd2VpZ2h0ID0gMTAwLCAjIE5vdCBhIGRpcmVjdCBlcXVpdmFsZW50IGJ1dCBzZXJ2ZXMgdG8gY29udHJvbCBvdmVyLWZpdHRpbmcKICBzdWJzYW1wbGUgPSAxLAogIGNvbHNhbXBsZV9ieXRyZWUgPSAxLCAjIEVxdWl2YWxlbnQgdG8gJ3NxcnQnIGluIG1heF9mZWF0dXJlcwogICMgTm90ZTogWEdCb29zdCBkb2VzIG5vdCBoYXZlIGEgZGlyZWN0IGVxdWl2YWxlbnQgZm9yICdtYXhfbGVhZl9ub2RlcycgYW5kICdpbml0JwogIGxhbWJkYSA9IDEwMAopCgojIE51bWJlciBvZiBib29zdGluZyByb3VuZHMgKGVxdWl2YWxlbnQgdG8gbl9lc3RpbWF0b3JzKQpucm91bmRzID0gNTAKCiMgVHJhaW4gdGhlIG1vZGVsCm1vZGVsID0geGdiLnRyYWluKHBhcmFtcyA9IHBhcmFtcywgZGF0YSA9IGR0cmFpbiwgbnJvdW5kcyA9IG5yb3VuZHMpCmBgYAoKR2V0IHByZWRpY3Rpb25zIGFuZCBzbW9vdGhlciBtYXRyaXg6CgpgYGB7ciwgcmVzdWx0cyA9ICdoaWRlJywgbWVzc2FnZSA9IEZBTFNFfQpsZWFmX2luZGljZXNfdHJhaW4gPSBwcmVkaWN0KG1vZGVsLCBkdHJhaW4sIHByZWRsZWFmID0gVFJVRSkKc21vb3RoZXJfdHJhaW5fWEcgPSBjcmVhdGVfU19mcm9tX2didHJlZ3Jlc3Nvcihtb2RlbCxsZWFmX2luZGljZXNfdHJhaW4sb3V0cHV0X2RpcixzYXZlX291dHB1dCA9IEZBTFNFKQpgYGAKClBsb3QgdGhlIHByZWRpY3Rpb246CgpgYGB7cn0KeV9oYXRfeGc9cHJlZGljdChtb2RlbCwgZHRyYWluKQoKdGliYmxlKHZhbHVlID0gYyh5X3RydWUseV9oYXRfS1JSX0dhdXNzaWFuLHlfaGF0X3JmLHlfaGF0X25wLHlfaGF0X3hnKSwKICAgICAgIFhfZ3JpZCA9IHJlcChYLDUpLAogICAgICAgTWV0aG9kID0gZmFjdG9yKGMocmVwKCJUcnVlIEZ1bmN0aW9uIiwgZGltKFgpWzFdKSxyZXAoIktSUiIsIGRpbShYKVsxXSksIHJlcCgiUmFuZG9tIEZvcmVzdCIsIGRpbShYKVsxXSksIHJlcCgiTlciLCBkaW0oWClbMV0pICwgcmVwKCJYR0Jvb3N0IiwgZGltKFgpWzFdKSAgICApKSkgJT4lIAogIGdncGxvdChhZXMoeCA9IHJlcChYLDUpLCB5ID0gcmVwKHksNSkpKSArCiAgZ2VvbV9wb2ludChhbHBoYSA9IDAuMDMpKwogIGdlb21fbGluZShhZXMoeCA9IFhfZ3JpZCwgeSA9IHZhbHVlLCBjb2xvciA9IE1ldGhvZCkpKwogIHNjYWxlX2NvbG9yX21hbnVhbCh2YWx1ZXMgPSBjKCJUcnVlIEZ1bmN0aW9uIiA9ICJibGFjayIsICJLUlIiID0gInJlZCIsICJSYW5kb20gRm9yZXN0IiA9ICJncmVlbiIsICJOVyIgPSAicHVycGxlIiwgIlhHQm9vc3QiID0gIm9yYW5nZSIpKSArCiAgdGhlbWVfbWluaW1hbCgpCmBgYAoKIyBFcXVpdmFsZW50IGtlcm5lbHM6CgpTZXQgc29tZSBwb2ludHMgd2hlcmUgd2Ugd2FudCB0aGUgZXF1aXZhbGVudCBrZXJuZWxzOgoKYGBge3J9CnBvaW50cyA9IGMoLTQsLTMsLTEuMDUsMC4wMSwxLjk1LDQpCiNwb2ludHMgPSBjKC00LC0zLjUsLTIsLTEuMDUsMC4wMSwxLjUsMS45NSwyLjUsNCkKcGxvdCA9IHRpYmJsZShYLHkpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSBYLCB5ID0geSkpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC4yKSsKICBnZW9tX2xpbmUoYWVzKHggPSBYLCB5ID0geV90cnVlKSwgY29sb3IgPSAiYmxhY2siKQoKZm9yIChpIGluIDE6bGVuZ3RoKHBvaW50cykpewogIHBsb3QgPSBwbG90K2dlb21fdmxpbmUoeGludGVyY2VwdCA9IHBvaW50c1tpXSwgbGluZXR5cGUgPSAiZGFzaGVkIikKICAKfSAgIApwbG90ICsgdGhlbWVfbWluaW1hbCgpCmBgYAoKIyMjIEV4dHJhY3QgdGhlIHdlaWdodHMKCkV4dHJhY3QgdGhlIGVxdWl2YWxlbnQga2VybmVscy93ZWlnaHRzIGFwcGxpZWQgYXQgdGhlc2UgcG9pbnRzOgoKYGBge3J9CiMgS1JSCnJlc3VsdHNfd2VpZ2h0c19LUlIgPSBtYXRyaXgoTkEsbnJvdyA9IGxlbmd0aChYKSwgbmNvbCA9IGxlbmd0aChwb2ludHMpKQpjb2xuYW1lcyhyZXN1bHRzX3dlaWdodHNfS1JSKSA9IHJlcCgiVGVtcCIsbGVuZ3RoKHBvaW50cykpCgojIFJlZ3Jlc3Npb24gRm9yZXN0CnJlc3VsdHNfd2VpZ2h0c19SRiA9IG1hdHJpeChOQSxucm93ID0gbGVuZ3RoKFgpLCBuY29sID0gbGVuZ3RoKHBvaW50cykpCmNvbG5hbWVzKHJlc3VsdHNfd2VpZ2h0c19SRikgPSByZXAoIlRlbXAiLGxlbmd0aChwb2ludHMpKQoKIyBOYWRheWFyYS1XYXRzb246CnJlc3VsdHNfd2VpZ2h0c19OVyA9IG1hdHJpeChOQSxucm93ID0gbGVuZ3RoKFgpLCBuY29sID0gbGVuZ3RoKHBvaW50cykpCmNvbG5hbWVzKHJlc3VsdHNfd2VpZ2h0c19OVykgPSByZXAoIlRlbXAiLGxlbmd0aChwb2ludHMpKQoKIyBYRyBCb29zdDoKcmVzdWx0c193ZWlnaHRzX1hHID0gbWF0cml4KE5BLG5yb3cgPSBsZW5ndGgoWCksIG5jb2wgPSBsZW5ndGgocG9pbnRzKSkKY29sbmFtZXMocmVzdWx0c193ZWlnaHRzX1hHKSA9IHJlcCgiVGVtcCIsbGVuZ3RoKHBvaW50cykpCgoKd2VpZ2h0c19LUlJfR2F1c3NpYW4gPSBweSR3ZWlnaHRfbWF0cml4X0dhdXNzaWFuCgoKCmZvciAoaSBpbiAxOmxlbmd0aChwb2ludHMpKXsKICAjIEtSUgogIHJlc3VsdHNfd2VpZ2h0c19LUlJbLGldID0gd2VpZ2h0c19LUlJfR2F1c3NpYW5bd2hpY2goYWJzKChhcy5udW1lcmljKFgpLXBvaW50c1tpXSkpPDAuMDAwMDAxKSxdCiAgY29sbmFtZXMocmVzdWx0c193ZWlnaHRzX0tSUilbaV0gPSBwYXN0ZTAoIng9Iixwb2ludHNbaV0pCiAgIyBSRjoKICByZXN1bHRzX3dlaWdodHNfUkZbLGldID0gbWF0cml4KGdldF9mb3Jlc3Rfd2VpZ2h0cyhyZWdfZm9yZXN0LGFzLm1hdHJpeChwb2ludHNbaV0pKSxuY29sID0gMSkKICBjb2xuYW1lcyhyZXN1bHRzX3dlaWdodHNfUkYpW2ldID0gcGFzdGUwKCJ4PSIscG9pbnRzW2ldKQogICAgIyBOVzoKICByZXN1bHRzX3dlaWdodHNfTldbLGldID0gZml0X21vZGVsJEhfb3B0W3doaWNoKGFicygoYXMubnVtZXJpYyhYKS1wb2ludHNbaV0pKTwwLjAwMDAwMSksXQogIGNvbG5hbWVzKHJlc3VsdHNfd2VpZ2h0c19OVylbaV0gPSBwYXN0ZTAoIng9Iixwb2ludHNbaV0pCiAgICAjIFhHCiAgcmVzdWx0c193ZWlnaHRzX1hHWyxpXSA9IHNtb290aGVyX3RyYWluX1hHW3doaWNoKGFicygoYXMubnVtZXJpYyhYKS1wb2ludHNbaV0pKTwwLjAwMDAwMSksXQogIGNvbG5hbWVzKHJlc3VsdHNfd2VpZ2h0c19YRylbaV0gPSBwYXN0ZTAoIng9Iixwb2ludHNbaV0pCiAgCn0KCmBgYAoKCiMjIyMjIEJvdW5kYXJ5IGFkYXB0aXZlbmVzcwoKYGBge3J9CnBvaW50c19ib3VuZGFyeSA9IGMoLTQuOTksLTQuNSwtNCwtMy41KQojcG9pbnRzID0gYygtNCwtMy41LC0yLC0xLjA1LDAuMDEsMS41LDEuOTUsMi41LDQpCnBsb3QgPSB0aWJibGUoeCA9IFhbMTpyb3VuZChsZW5ndGgoeSkvMiksXSx5ID0geVsxOnJvdW5kKGxlbmd0aChYKS8yKV0pICU+JSAKICBnZ3Bsb3QoYWVzKHggPSB4LCB5ID0geSkpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC4yKSsKICBnZW9tX2xpbmUoYWVzKHggPSB4LCB5ID0geV90cnVlWzE6cm91bmQobGVuZ3RoKFgpLzIpXSksIGNvbG9yID0gImJsYWNrIikKCmZvciAoaSBpbiAxOmxlbmd0aChwb2ludHNfYm91bmRhcnkpKXsKICBwbG90ID0gcGxvdCtnZW9tX3ZsaW5lKHhpbnRlcmNlcHQgPSBwb2ludHNfYm91bmRhcnlbaV0sIGxpbmV0eXBlID0gImRhc2hlZCIpCiAgCn0gICAKcGxvdCArIHRoZW1lX21pbmltYWwoKQpgYGAKCkV4dHJhY3QgdGhlIGVxdWl2YWxlbnQga2VybmVscy93ZWlnaHRzIGFwcGxpZWQgYXQgdGhlc2UgcG9pbnRzOgoKYGBge3J9CiMgS1JSCnJlc3VsdHNfd2VpZ2h0c19LUlJfYm91bmRhcnkgPSBtYXRyaXgoTkEsbnJvdyA9IGxlbmd0aChYKSwgbmNvbCA9IGxlbmd0aChwb2ludHNfYm91bmRhcnkpKQpjb2xuYW1lcyhyZXN1bHRzX3dlaWdodHNfS1JSX2JvdW5kYXJ5KSA9IHJlcCgiVGVtcCIsbGVuZ3RoKHBvaW50c19ib3VuZGFyeSkpCgojIFJlZ3Jlc3Npb24gRm9yZXN0CnJlc3VsdHNfd2VpZ2h0c19SRl9ib3VuZGFyeSA9IG1hdHJpeChOQSxucm93ID0gbGVuZ3RoKFgpLCBuY29sID0gbGVuZ3RoKHBvaW50c19ib3VuZGFyeSkpCmNvbG5hbWVzKHJlc3VsdHNfd2VpZ2h0c19SRl9ib3VuZGFyeSkgPSByZXAoIlRlbXAiLGxlbmd0aChwb2ludHNfYm91bmRhcnkpKQoKIyBOYWRheWFyYS1XYXRzb246CnJlc3VsdHNfd2VpZ2h0c19OV19ib3VuZGFyeSA9IG1hdHJpeChOQSxucm93ID0gbGVuZ3RoKFgpLCBuY29sID0gbGVuZ3RoKHBvaW50c19ib3VuZGFyeSkpCmNvbG5hbWVzKHJlc3VsdHNfd2VpZ2h0c19OV19ib3VuZGFyeSkgPSByZXAoIlRlbXAiLGxlbmd0aChwb2ludHNfYm91bmRhcnkpKQoKIyBYR0Jvb3N0OgpyZXN1bHRzX3dlaWdodHNfWEdfYm91bmRhcnkgPSBtYXRyaXgoTkEsbnJvdyA9IGxlbmd0aChYKSwgbmNvbCA9IGxlbmd0aChwb2ludHNfYm91bmRhcnkpKQpjb2xuYW1lcyhyZXN1bHRzX3dlaWdodHNfWEdfYm91bmRhcnkpID0gcmVwKCJUZW1wIixsZW5ndGgocG9pbnRzX2JvdW5kYXJ5KSkKCgp3ZWlnaHRzX0tSUl9HYXVzc2lhbiA9IHB5JHdlaWdodF9tYXRyaXhfR2F1c3NpYW4KCmZvciAoaSBpbiAxOmxlbmd0aChwb2ludHNfYm91bmRhcnkpKXsKICAjIEtSUgogIHJlc3VsdHNfd2VpZ2h0c19LUlJfYm91bmRhcnlbLGldID0gd2VpZ2h0c19LUlJfR2F1c3NpYW5bd2hpY2goYWJzKChhcy5udW1lcmljKFgpLXBvaW50c19ib3VuZGFyeVtpXSkpPDAuMDAwMDAxKSxdCiAgY29sbmFtZXMocmVzdWx0c193ZWlnaHRzX0tSUl9ib3VuZGFyeSlbaV0gPSBwYXN0ZTAoIng9Iixwb2ludHNfYm91bmRhcnlbaV0pCiAgIyBSRjoKICByZXN1bHRzX3dlaWdodHNfUkZfYm91bmRhcnlbLGldID0gbWF0cml4KGdldF9mb3Jlc3Rfd2VpZ2h0cyhyZWdfZm9yZXN0LGFzLm1hdHJpeChwb2ludHNfYm91bmRhcnlbaV0pKSxuY29sID0gMSkKICBjb2xuYW1lcyhyZXN1bHRzX3dlaWdodHNfUkZfYm91bmRhcnkpW2ldID0gcGFzdGUwKCJ4PSIscG9pbnRzX2JvdW5kYXJ5W2ldKQogICMgTlc6CiAgcmVzdWx0c193ZWlnaHRzX05XX2JvdW5kYXJ5WyxpXSA9IGZpdF9tb2RlbCRIX29wdFt3aGljaChhYnMoKGFzLm51bWVyaWMoWCktcG9pbnRzX2JvdW5kYXJ5W2ldKSk8MC4wMDAwMDEpLF0KICBjb2xuYW1lcyhyZXN1bHRzX3dlaWdodHNfTldfYm91bmRhcnkpW2ldID0gcGFzdGUwKCJ4PSIscG9pbnRzX2JvdW5kYXJ5W2ldKQogICMgWEcKICByZXN1bHRzX3dlaWdodHNfWEdfYm91bmRhcnlbLGldID0gc21vb3RoZXJfdHJhaW5fWEdbd2hpY2goYWJzKChhcy5udW1lcmljKFgpLXBvaW50c19ib3VuZGFyeVtpXSkpPDAuMDAwMDAxKSxdCiAgY29sbmFtZXMocmVzdWx0c193ZWlnaHRzX1hHX2JvdW5kYXJ5KVtpXSA9IHBhc3RlMCgieD0iLHBvaW50c1tpXSkKICAKfQoKYGBgCgoKIyMjIFZpc3VhbGl6ZSBLUlIKClZpc3VhbGl6ZSBmb3IgS1JSOgoKCmBgYHtyfQpyZXN1bHRzX3dlaWdodHNfS1JSID0gYXNfdGliYmxlKHJlc3VsdHNfd2VpZ2h0c19LUlIpCnJlc3VsdHNfd2VpZ2h0c19LUlIgPSByZXN1bHRzX3dlaWdodHNfS1JSICU+JSBtdXRhdGUoWCA9IGFzLm51bWVyaWMoWCkpICU+JSBwaXZvdF9sb25nZXIoY29scyA9IHN0YXJ0c193aXRoKCJ4PSIpLCBuYW1lc190byA9ICJ4IiwgbmFtZXNfcHJlZml4ID0gIng9IiwgdmFsdWVzX3RvID0gIndlaWdodCIpICU+JSBtdXRhdGUoeCA9IGFzX2ZhY3Rvcih4KSkKCnJlc3VsdHNfd2VpZ2h0c19LUlIgJT4lCiAgZ2dwbG90KGFlcyh4ID0gWCwgeSA9IHdlaWdodCwgY29sb3IgPSB4KSkrCiAgZ2VvbV9saW5lKCkrCiAgdGhlbWVfbWluaW1hbCgpCmBgYAoKIyMjIyMgQm91bmRhcnkKClBsb3Q6CgpgYGB7cn0KcmVzdWx0c193ZWlnaHRzX0tSUl9ib3VuZGFyeSA9IGFzX3RpYmJsZShyZXN1bHRzX3dlaWdodHNfS1JSX2JvdW5kYXJ5KQpyZXN1bHRzX3dlaWdodHNfS1JSX2JvdW5kYXJ5ID0gcmVzdWx0c193ZWlnaHRzX0tSUl9ib3VuZGFyeSAlPiUgc2xpY2VfaGVhZChuID0gcm91bmQobGVuZ3RoKHkpLzIpKSAlPiUgbXV0YXRlKFggPSBhcy5udW1lcmljKFhbMTpyb3VuZChsZW5ndGgoeSkvMiksXSkpICU+JSBwaXZvdF9sb25nZXIoY29scyA9IHN0YXJ0c193aXRoKCJ4PSIpLCBuYW1lc190byA9ICJ4IiwgbmFtZXNfcHJlZml4ID0gIng9IiwgdmFsdWVzX3RvID0gIndlaWdodCIpICU+JSBtdXRhdGUoeCA9IGFzX2ZhY3Rvcih4KSkKCnJlc3VsdHNfd2VpZ2h0c19LUlJfYm91bmRhcnkgJT4lCiAgZ2dwbG90KGFlcyh4ID0gWCwgeSA9IHdlaWdodCwgY29sb3IgPSB4KSkrCiAgZ2VvbV9saW5lKCkrCiAgdGhlbWVfbWluaW1hbCgpCmBgYAoKIyMjIFZpc3VhbGl6ZSBSRgoKVmlzdWFsaXplIGZvciByZWdyZXNzaW9uIGZvcmVzdDoKCgpgYGB7cn0KcmVzdWx0c193ZWlnaHRzX1JGID0gYXNfdGliYmxlKHJlc3VsdHNfd2VpZ2h0c19SRikKcmVzdWx0c193ZWlnaHRzX1JGID0gcmVzdWx0c193ZWlnaHRzX1JGICU+JSBtdXRhdGUoWCA9IGFzLm51bWVyaWMoWCkpICU+JSBwaXZvdF9sb25nZXIoY29scyA9IHN0YXJ0c193aXRoKCJ4PSIpLCBuYW1lc190byA9ICJ4IiwgbmFtZXNfcHJlZml4ID0gIng9IiwgdmFsdWVzX3RvID0gIndlaWdodCIpICU+JSBtdXRhdGUoeCA9IGFzX2ZhY3Rvcih4KSkKCnJlc3VsdHNfd2VpZ2h0c19SRiAlPiUKICBnZ3Bsb3QoYWVzKHggPSBYLCB5ID0gd2VpZ2h0LCBjb2xvciA9IHgpKSsKICBnZW9tX2xpbmUoKSsKICB0aGVtZV9taW5pbWFsKCkKYGBgCgojIyMjIyBCb3VuZGFyeQoKYGBge3J9CnJlc3VsdHNfd2VpZ2h0c19SRl9ib3VuZGFyeSA9IGFzX3RpYmJsZShyZXN1bHRzX3dlaWdodHNfUkZfYm91bmRhcnkpCnJlc3VsdHNfd2VpZ2h0c19SRl9ib3VuZGFyeSA9IHJlc3VsdHNfd2VpZ2h0c19SRl9ib3VuZGFyeSAlPiUgc2xpY2VfaGVhZChuID0gcm91bmQobGVuZ3RoKHkpLzIpKSAlPiUgbXV0YXRlKFggPSBhcy5udW1lcmljKFhbMTpyb3VuZChsZW5ndGgoeSkvMiksXSkpICU+JSBwaXZvdF9sb25nZXIoY29scyA9IHN0YXJ0c193aXRoKCJ4PSIpLCBuYW1lc190byA9ICJ4IiwgbmFtZXNfcHJlZml4ID0gIng9IiwgdmFsdWVzX3RvID0gIndlaWdodCIpICU+JSBtdXRhdGUoeCA9IGFzX2ZhY3Rvcih4KSkKCnJlc3VsdHNfd2VpZ2h0c19SRl9ib3VuZGFyeSAlPiUKICBnZ3Bsb3QoYWVzKHggPSBYLCB5ID0gd2VpZ2h0LCBjb2xvciA9IHgpKSsKICBnZW9tX2xpbmUoKSsKICB0aGVtZV9taW5pbWFsKCkKYGBgCiMjIyBWaXN1YWxpemUgTlc6CgpgYGB7cn0KcmVzdWx0c193ZWlnaHRzX05XID0gYXNfdGliYmxlKHJlc3VsdHNfd2VpZ2h0c19OVykKcmVzdWx0c193ZWlnaHRzX05XID0gcmVzdWx0c193ZWlnaHRzX05XICU+JSBtdXRhdGUoWCA9IGFzLm51bWVyaWMoWCkpICU+JSBwaXZvdF9sb25nZXIoY29scyA9IHN0YXJ0c193aXRoKCJ4PSIpLCBuYW1lc190byA9ICJ4IiwgbmFtZXNfcHJlZml4ID0gIng9IiwgdmFsdWVzX3RvID0gIndlaWdodCIpICU+JSBtdXRhdGUoeCA9IGFzX2ZhY3Rvcih4KSkKCnJlc3VsdHNfd2VpZ2h0c19OVyAlPiUKICBnZ3Bsb3QoYWVzKHggPSBYLCB5ID0gd2VpZ2h0LCBjb2xvciA9IHgpKSsKICBnZW9tX2xpbmUoKSsKICB0aGVtZV9taW5pbWFsKCkKYGBgCgojIyMjIyBCb3VuZGFyeQoKYGBge3J9CnJlc3VsdHNfd2VpZ2h0c19OV19ib3VuZGFyeSA9IGFzX3RpYmJsZShyZXN1bHRzX3dlaWdodHNfTldfYm91bmRhcnkpCnJlc3VsdHNfd2VpZ2h0c19OV19ib3VuZGFyeSA9IHJlc3VsdHNfd2VpZ2h0c19OV19ib3VuZGFyeSAlPiUgc2xpY2VfaGVhZChuID0gcm91bmQobGVuZ3RoKHkpLzIpKSAlPiUgbXV0YXRlKFggPSBhcy5udW1lcmljKFhbMTpyb3VuZChsZW5ndGgoeSkvMiksXSkpICU+JSBwaXZvdF9sb25nZXIoY29scyA9IHN0YXJ0c193aXRoKCJ4PSIpLCBuYW1lc190byA9ICJ4IiwgbmFtZXNfcHJlZml4ID0gIng9IiwgdmFsdWVzX3RvID0gIndlaWdodCIpICU+JSBtdXRhdGUoeCA9IGFzX2ZhY3Rvcih4KSkKCnJlc3VsdHNfd2VpZ2h0c19OV19ib3VuZGFyeSAlPiUKICBnZ3Bsb3QoYWVzKHggPSBYLCB5ID0gd2VpZ2h0LCBjb2xvciA9IHgpKSsKICBnZW9tX2xpbmUoKSsKICB0aGVtZV9taW5pbWFsKCkKYGBgCiMjIyBWaXN1YWxpemUgWEcKCmBgYHtyfQpyZXN1bHRzX3dlaWdodHNfWEcgPSBhc190aWJibGUocmVzdWx0c193ZWlnaHRzX1hHKQpyZXN1bHRzX3dlaWdodHNfWEcgPSByZXN1bHRzX3dlaWdodHNfWEcgJT4lIG11dGF0ZShYID0gYXMubnVtZXJpYyhYKSkgJT4lIHBpdm90X2xvbmdlcihjb2xzID0gc3RhcnRzX3dpdGgoIng9IiksIG5hbWVzX3RvID0gIngiLCBuYW1lc19wcmVmaXggPSAieD0iLCB2YWx1ZXNfdG8gPSAid2VpZ2h0IikgJT4lIG11dGF0ZSh4ID0gYXNfZmFjdG9yKHgpKQoKcmVzdWx0c193ZWlnaHRzX1hHICU+JQogIGdncGxvdChhZXMoeCA9IFgsIHkgPSB3ZWlnaHQsIGNvbG9yID0geCkpKwogIGdlb21fbGluZSgpKwogIHRoZW1lX21pbmltYWwoKQpgYGAKIyMjIyMgQm91bmRhcnkKCmBgYHtyfQpyZXN1bHRzX3dlaWdodHNfWEdfYm91bmRhcnkgPSBhc190aWJibGUocmVzdWx0c193ZWlnaHRzX1hHX2JvdW5kYXJ5KQpyZXN1bHRzX3dlaWdodHNfWEdfYm91bmRhcnkgPSByZXN1bHRzX3dlaWdodHNfWEdfYm91bmRhcnkgJT4lIHNsaWNlX2hlYWQobiA9IHJvdW5kKGxlbmd0aCh5KS8yKSkgJT4lIG11dGF0ZShYID0gYXMubnVtZXJpYyhYWzE6cm91bmQobGVuZ3RoKHkpLzIpLF0pKSAlPiUgcGl2b3RfbG9uZ2VyKGNvbHMgPSBzdGFydHNfd2l0aCgieD0iKSwgbmFtZXNfdG8gPSAieCIsIG5hbWVzX3ByZWZpeCA9ICJ4PSIsIHZhbHVlc190byA9ICJ3ZWlnaHQiKSAlPiUgbXV0YXRlKHggPSBhc19mYWN0b3IoeCkpCgpyZXN1bHRzX3dlaWdodHNfWEdfYm91bmRhcnkgJT4lCiAgZ2dwbG90KGFlcyh4ID0gWCwgeSA9IHdlaWdodCwgY29sb3IgPSB4KSkrCiAgZ2VvbV9saW5lKCkrCiAgdGhlbWVfbWluaW1hbCgpCmBgYAoKIyBOZXcgRnVuY3Rpb24sIGp1c3QgYSBsaW5lCgpDcmVhdGUgYSAic2ltcGxlIiBmdW5jdGlvbjoKCmBgYHtyfQp5X2Z1bmN0aW9uID0gZnVuY3Rpb24oeCl7CiAgeSA9IDAuNSp4CiAgcmV0dXJuKHkpCn0KYGBgCgpEcmF3IGFuZCB2aXN1YWxpemUgYSByZWFsaXphdGlvbiBmb3IgJHAgPSAxJC4gT2JzZXJ2YXRpb25zIHNjYXR0ZXJlZCB1bmV2ZW5seSBhbG9uZyB0aGUgJHgkLWF4aXM6CgpgYGB7cn0Kc2V0LnNlZWQoMTIzNCkKcCA9IDEKWCA9IG1hdHJpeChjKHJ1bmlmKDUwMCwtNSwtMikscnVuaWYoNTAsLTIsMSkscnVuaWYoMTAwMCwxLDMpLHJ1bmlmKDEwMCwzLDUpKSxuY29sID0gMSkKeSA9IHlfZnVuY3Rpb24oWCkgKyBybm9ybShkaW0oWClbMV0sc2QgPSAwLjIpCnlfdHJ1ZSA9IHlfZnVuY3Rpb24oWCkKdGliYmxlKFgseSkgJT4lIAogIGdncGxvdChhZXMoeCA9IFgsIHkgPSB5KSkgKwogIGdlb21fcG9pbnQoYWxwaGEgPSAwLjIpKwogIGdlb21fbGluZShhZXMoeCA9IFgsIHkgPSB5X3RydWUpLCBjb2xvciA9ICJibGFjayIpKwogIHRoZW1lX21pbmltYWwoKQpgYGAKCiMgRml0IHRoZSBmdW5jdGlvbjoKCiMjIyBLZXJuZWwgUmlkZ2UgUmVncmVzc2lvbjoKCkZpdCBieSBLUlI6CgoKYGBge3B5dGhvbn0KcGFyYW1fZGlzdHJpYnV0aW9uc19HYXVzc2lhbiA9IHsKICAiYWxwaGEiOiB1bmlmb3JtKDFlLTksIDEpLAogICJrZXJuZWxfX2xlbmd0aF9zY2FsZSI6IHVuaWZvcm0oMWUtOSwgMS41KSwKfQoKS1JSX0NWX0dhdXNzaWFuID0gUmFuZG9taXplZFNlYXJjaENWKAogICAgS2VybmVsUmlkZ2Uoa2VybmVsID0gUkJGKCkpLAogICAgcGFyYW1fZGlzdHJpYnV0aW9ucz1wYXJhbV9kaXN0cmlidXRpb25zX0dhdXNzaWFuLAogICAgbl9pdGVyPTUwMCwKICAgIG5fam9icz0tMQogICAgKQpfID0gS1JSX0NWX0dhdXNzaWFuLmZpdChyLlgsci55KSAjIGZpdCB0aGUga2VybmVsIHJpZGdlIHJlZ3Jlc3Npb24gdXNpbmcgY3Jvc3MudmFsaWRhdGVkIGxhbWJkYSwgc3VwcHJlc3NlcyBvdXRwdXQKI0tSUl9DVl9HYXVzc2lhbi5iZXN0X3BhcmFtc18KeV9oYXRfS1JSX0dhdXNzaWFuID0gS1JSX0NWX0dhdXNzaWFuLnByZWRpY3Qoci5YKQpLID0gUkJGKGxlbmd0aF9zY2FsZSA9IEtSUl9DVl9HYXVzc2lhbi5iZXN0X3BhcmFtc19bJ2tlcm5lbF9fbGVuZ3RoX3NjYWxlJ10sbGVuZ3RoX3NjYWxlX2JvdW5kcyA9ICJmaXhlZCIpCktfbWF0ID0gSyhyLlgpCmludiA9IG5wLmxpbmFsZy5pbnYoS19tYXQgKyBLUlJfQ1ZfR2F1c3NpYW4uYmVzdF9wYXJhbXNfWydhbHBoYSddKm5wLmV5ZShLX21hdC5zaGFwZVswXSkpIAp3ZWlnaHRfbWF0cml4X0dhdXNzaWFuID0gS19tYXRAIGludiAjIHdlaWdodCBtYXRyaXgKYGBgCgpWaXN1YWxpemU6CgpgYGB7cn0KeV9oYXRfS1JSX0dhdXNzaWFuID0gYXMubnVtZXJpYyhweSR5X2hhdF9LUlJfR2F1c3NpYW4pCgp0aWJibGUodmFsdWUgPSBjKHlfdHJ1ZSx5X2hhdF9LUlJfR2F1c3NpYW4pLAogICAgICAgWF9ncmlkID0gcmVwKFgsMiksCiAgICAgICBNZXRob2QgPSBmYWN0b3IoYyhyZXAoIlRydWUgRnVuY3Rpb24iLCBkaW0oWClbMV0pLHJlcCgiS1JSIiwgZGltKFgpWzFdKSkpKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gcmVwKFgsMiksIHkgPSByZXAoeSwyKSkpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC4yKSsKICBnZW9tX2xpbmUoYWVzKHggPSBYX2dyaWQsIHkgPSB2YWx1ZSwgY29sb3IgPSBNZXRob2QpKSsKICBzY2FsZV9jb2xvcl9tYW51YWwodmFsdWVzID0gYygiVHJ1ZSBGdW5jdGlvbiIgPSAiYmxhY2siLCAiS1JSIiA9ICJyZWQiKSkgKwogIHRoZW1lX21pbmltYWwoKQpgYGAKCiMjIyBSZWdyZXNzaW9uIEZvcmVzdDoKCmBgYHtyfQpyZWdfZm9yZXN0ID0gcmVncmVzc2lvbl9mb3Jlc3QoWCx5LCB0dW5lLnBhcmFtZXRlcnMgPSAiYWxsIikKeV9oYXRfcmYgPSBwcmVkaWN0KHJlZ19mb3Jlc3QsIFgpJHByZWRpY3Rpb25zCgp0aWJibGUodmFsdWUgPSBjKHlfdHJ1ZSx5X2hhdF9LUlJfR2F1c3NpYW4seV9oYXRfcmYpLAogICAgICAgWF9ncmlkID0gcmVwKFgsMyksCiAgICAgICBNZXRob2QgPSBmYWN0b3IoYyhyZXAoIlRydWUgRnVuY3Rpb24iLCBkaW0oWClbMV0pLHJlcCgiS1JSIiwgZGltKFgpWzFdKSwgcmVwKCJSYW5kb20gRm9yZXN0IiwgZGltKFgpWzFdKSkpKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gcmVwKFgsMyksIHkgPSByZXAoeSwzKSkpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC4xKSsKICBnZW9tX2xpbmUoYWVzKHggPSBYX2dyaWQsIHkgPSB2YWx1ZSwgY29sb3IgPSBNZXRob2QpKSsKICBzY2FsZV9jb2xvcl9tYW51YWwodmFsdWVzID0gYygiVHJ1ZSBGdW5jdGlvbiIgPSAiYmxhY2siLCAiS1JSIiA9ICJyZWQiLCAiUmFuZG9tIEZvcmVzdCIgPSAiZ3JlZW4iKSkgKwogIHRoZW1lX21pbmltYWwoKQpgYGAKCiMjIyBOYWRheWFyYS1XYXRzb24KYGBge3J9CmZpdF9tb2RlbCA9IGZpdF9rZXJuX1JlZ19HQ1ZfcGFyYWxsZWwoWCxYLHksMC4wMSwxKQp5X2hhdF9ucCA9IGZpdF9tb2RlbCRwcmVkaWN0aW9ucwoKdGliYmxlKHZhbHVlID0gYyh5X3RydWUseV9oYXRfS1JSX0dhdXNzaWFuLHlfaGF0X3JmLHlfaGF0X25wKSwKICAgICAgIFhfZ3JpZCA9IHJlcChYLDQpLAogICAgICAgTWV0aG9kID0gZmFjdG9yKGMocmVwKCJUcnVlIEZ1bmN0aW9uIiwgZGltKFgpWzFdKSxyZXAoIktSUiIsIGRpbShYKVsxXSksIHJlcCgiUmFuZG9tIEZvcmVzdCIsIGRpbShYKVsxXSksIHJlcCgiTlciLCBkaW0oWClbMV0pICAgICkpKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gcmVwKFgsNCksIHkgPSByZXAoeSw0KSkpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC4wNykrCiAgZ2VvbV9saW5lKGFlcyh4ID0gWF9ncmlkLCB5ID0gdmFsdWUsIGNvbG9yID0gTWV0aG9kKSkrCiAgc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcyA9IGMoIlRydWUgRnVuY3Rpb24iID0gImJsYWNrIiwgIktSUiIgPSAicmVkIiwgIlJhbmRvbSBGb3Jlc3QiID0gImdyZWVuIiwgIk5XIiA9ICJwdXJwbGUiKSkgKwogIHRoZW1lX21pbmltYWwoKQpgYGAKIyMjIFhHIEJvb3N0CgpTZXQgdXA6CgpgYGB7cn0KIyBDb252ZXJ0IHRvIERNYXRyaXggb2JqZWN0CmR0cmFpbiA9IHhnYi5ETWF0cml4KGRhdGEgPSBhcy5tYXRyaXgoWCksIGxhYmVsID0geSkKI2R0ZXN0ID0geGdiLkRNYXRyaXgoZGF0YSA9IGFzLm1hdHJpeCh0ZXN0X2ZlYXR1cmVzKSwgbGFiZWwgPSB0ZXN0X3RhcmdldHMpCgojIERlZmluZSBtb2RlbCBwYXJhbWV0ZXJzCnBhcmFtcyA9IGxpc3QoCiAgYm9vc3RlciA9ICJnYnRyZWUiLAogIG9iamVjdGl2ZSA9ICJyZWc6c3F1YXJlZGVycm9yIiwKICBldGEgPSAwLjg1LCAjIEVxdWl2YWxlbnQgdG8gbGVhcm5pbmdfcmF0ZQogIG1heF9kZXB0aCA9IDYsICMgTmVlZCB0byBzcGVjaWZ5IGEgdmFsdWUgYXMgWEdCb29zdCByZXF1aXJlcyBhIG51bWVyaWNhbCB2YWx1ZQogIG1pbl9jaGlsZF93ZWlnaHQgPSA1MCwgIyBOb3QgYSBkaXJlY3QgZXF1aXZhbGVudCBidXQgc2VydmVzIHRvIGNvbnRyb2wgb3Zlci1maXR0aW5nCiAgc3Vic2FtcGxlID0gMSwKICBjb2xzYW1wbGVfYnl0cmVlID0gMSwgIyBFcXVpdmFsZW50IHRvICdzcXJ0JyBpbiBtYXhfZmVhdHVyZXMKICAjIE5vdGU6IFhHQm9vc3QgZG9lcyBub3QgaGF2ZSBhIGRpcmVjdCBlcXVpdmFsZW50IGZvciAnbWF4X2xlYWZfbm9kZXMnIGFuZCAnaW5pdCcKICBsYW1iZGEgPSAxCikKCiMgTnVtYmVyIG9mIGJvb3N0aW5nIHJvdW5kcyAoZXF1aXZhbGVudCB0byBuX2VzdGltYXRvcnMpCm5yb3VuZHMgPSA1MAoKIyBUcmFpbiB0aGUgbW9kZWwKbW9kZWwgPSB4Z2IudHJhaW4ocGFyYW1zID0gcGFyYW1zLCBkYXRhID0gZHRyYWluLCBucm91bmRzID0gbnJvdW5kcykKYGBgCgpHZXQgcHJlZGljdGlvbnMgYW5kIHNtb290aGVyIG1hdHJpeDoKCmBgYHtyLCByZXN1bHRzID0gJ2hpZGUnLCBtZXNzYWdlID0gRkFMU0V9CmxlYWZfaW5kaWNlc190cmFpbiA9IHByZWRpY3QobW9kZWwsIGR0cmFpbiwgcHJlZGxlYWYgPSBUUlVFKQpzbW9vdGhlcl90cmFpbl9YRyA9IGNyZWF0ZV9TX2Zyb21fZ2J0cmVncmVzc29yKG1vZGVsLGxlYWZfaW5kaWNlc190cmFpbixvdXRwdXRfZGlyLHNhdmVfb3V0cHV0ID0gRkFMU0UpCmBgYAoKUGxvdCB0aGUgcHJlZGljdGlvbjoKCmBgYHtyfQp5X2hhdF94Zz1wcmVkaWN0KG1vZGVsLCBkdHJhaW4pCgp0aWJibGUodmFsdWUgPSBjKHlfdHJ1ZSx5X2hhdF9LUlJfR2F1c3NpYW4seV9oYXRfcmYseV9oYXRfbnAseV9oYXRfeGcpLAogICAgICAgWF9ncmlkID0gcmVwKFgsNSksCiAgICAgICBNZXRob2QgPSBmYWN0b3IoYyhyZXAoIlRydWUgRnVuY3Rpb24iLCBkaW0oWClbMV0pLHJlcCgiS1JSIiwgZGltKFgpWzFdKSwgcmVwKCJSYW5kb20gRm9yZXN0IiwgZGltKFgpWzFdKSwgcmVwKCJOVyIsIGRpbShYKVsxXSkgLCByZXAoIlhHQm9vc3QiLCBkaW0oWClbMV0pICAgICkpKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gcmVwKFgsNSksIHkgPSByZXAoeSw1KSkpICsKICBnZW9tX3BvaW50KGFscGhhID0gMC4wMykrCiAgZ2VvbV9saW5lKGFlcyh4ID0gWF9ncmlkLCB5ID0gdmFsdWUsIGNvbG9yID0gTWV0aG9kKSkrCiAgc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcyA9IGMoIlRydWUgRnVuY3Rpb24iID0gImJsYWNrIiwgIktSUiIgPSAicmVkIiwgIlJhbmRvbSBGb3Jlc3QiID0gImdyZWVuIiwgIk5XIiA9ICJwdXJwbGUiLCAiWEdCb29zdCIgPSAib3JhbmdlIikpICsKICB0aGVtZV9taW5pbWFsKCkKYGBgCiMgRXF1aXZhbGVudCBrZXJuZWxzCgpTZXQgc29tZSBwb2ludHMgd2hlcmUgd2Ugd2FudCB0aGUgZXF1aXZhbGVudCBrZXJuZWxzOgoKYGBge3J9CnBvaW50cyA9IHF1YW50aWxlKFgscHJvYnMgPSBjKDAuMSwwLjIsMC4zMSwwLjMyLDAuMzUsMC43LDAuOTgpLCB0eXBlID0gMSkKI3BvaW50cyA9IGMoLTQsLTMuNSwtMiwtMS4wNSwwLjAxLDEuNSwxLjk1LDIuNSw0KQpwbG90ID0gdGliYmxlKFgseSkgJT4lIAogIGdncGxvdChhZXMoeCA9IFgsIHkgPSB5KSkgKwogIGdlb21fcG9pbnQoYWxwaGEgPSAwLjIpKwogIGdlb21fbGluZShhZXMoeCA9IFgsIHkgPSB5X3RydWUpLCBjb2xvciA9ICJibGFjayIpCgpmb3IgKGkgaW4gMTpsZW5ndGgocG9pbnRzKSl7CiAgcGxvdCA9IHBsb3QrZ2VvbV92bGluZSh4aW50ZXJjZXB0ID0gcG9pbnRzW2ldLCBsaW5ldHlwZSA9ICJkYXNoZWQiKQogIAp9ICAgCnBsb3QgKyB0aGVtZV9taW5pbWFsKCkKYGBgCgojIyMgRXh0cmFjdCB0aGUgd2VpZ2h0czoKCkV4dHJhY3QgdGhlIGVxdWl2YWxlbnQga2VybmVscy93ZWlnaHRzIGFwcGxpZWQgYXQgdGhlc2UgcG9pbnRzOgoKYGBge3J9CiMgS1JSCnJlc3VsdHNfd2VpZ2h0c19LUlIgPSBtYXRyaXgoTkEsbnJvdyA9IGxlbmd0aChYKSwgbmNvbCA9IGxlbmd0aChwb2ludHMpKQpjb2xuYW1lcyhyZXN1bHRzX3dlaWdodHNfS1JSKSA9IHJlcCgiVGVtcCIsbGVuZ3RoKHBvaW50cykpCgojIFJlZ3Jlc3Npb24gRm9yZXN0CnJlc3VsdHNfd2VpZ2h0c19SRiA9IG1hdHJpeChOQSxucm93ID0gbGVuZ3RoKFgpLCBuY29sID0gbGVuZ3RoKHBvaW50cykpCmNvbG5hbWVzKHJlc3VsdHNfd2VpZ2h0c19SRikgPSByZXAoIlRlbXAiLGxlbmd0aChwb2ludHMpKQoKIyBOYWRheWFyYS1XYXRzb246CnJlc3VsdHNfd2VpZ2h0c19OVyA9IG1hdHJpeChOQSxucm93ID0gbGVuZ3RoKFgpLCBuY29sID0gbGVuZ3RoKHBvaW50cykpCmNvbG5hbWVzKHJlc3VsdHNfd2VpZ2h0c19OVykgPSByZXAoIlRlbXAiLGxlbmd0aChwb2ludHMpKQoKIyBYRyBCb29zdDoKcmVzdWx0c193ZWlnaHRzX1hHID0gbWF0cml4KE5BLG5yb3cgPSBsZW5ndGgoWCksIG5jb2wgPSBsZW5ndGgocG9pbnRzKSkKY29sbmFtZXMocmVzdWx0c193ZWlnaHRzX1hHKSA9IHJlcCgiVGVtcCIsbGVuZ3RoKHBvaW50cykpCgp3ZWlnaHRzX0tSUl9HYXVzc2lhbiA9IHB5JHdlaWdodF9tYXRyaXhfR2F1c3NpYW4KCmZvciAoaSBpbiAxOmxlbmd0aChwb2ludHMpKXsKICAjIEtSUgogIHJlc3VsdHNfd2VpZ2h0c19LUlJbLGldID0gd2VpZ2h0c19LUlJfR2F1c3NpYW5bd2hpY2goYWJzKChhcy5udW1lcmljKFgpLXBvaW50c1tpXSkpPDAuMDAwMDAxKSxdCiAgY29sbmFtZXMocmVzdWx0c193ZWlnaHRzX0tSUilbaV0gPSBwYXN0ZTAoIng9Iixwb2ludHNbaV0pCiAgIyBSRjoKICByZXN1bHRzX3dlaWdodHNfUkZbLGldID0gbWF0cml4KGdldF9mb3Jlc3Rfd2VpZ2h0cyhyZWdfZm9yZXN0LGFzLm1hdHJpeChwb2ludHNbaV0pKSxuY29sID0gMSkKICBjb2xuYW1lcyhyZXN1bHRzX3dlaWdodHNfUkYpW2ldID0gcGFzdGUwKCJ4PSIscG9pbnRzW2ldKQogICMgTlc6CiAgcmVzdWx0c193ZWlnaHRzX05XWyxpXSA9IGZpdF9tb2RlbCRIX29wdFt3aGljaChhYnMoKGFzLm51bWVyaWMoWCktcG9pbnRzW2ldKSk8MC4wMDAwMDEpLF0KICBjb2xuYW1lcyhyZXN1bHRzX3dlaWdodHNfTlcpW2ldID0gcGFzdGUwKCJ4PSIscG9pbnRzW2ldKQogICMgWEcKICByZXN1bHRzX3dlaWdodHNfWEdbLGldID0gc21vb3RoZXJfdHJhaW5fWEdbd2hpY2goYWJzKChhcy5udW1lcmljKFgpLXBvaW50c1tpXSkpPDAuMDAwMDAxKSxdCiAgY29sbmFtZXMocmVzdWx0c193ZWlnaHRzX1hHKVtpXSA9IHBhc3RlMCgieD0iLHBvaW50c1tpXSkKICAKfQoKYGBgCgojIyMgVmlzdWFsaXplIEtSUgoKVmlzdWFsaXplIGZvciBLUlI6CgoKYGBge3J9CnJlc3VsdHNfd2VpZ2h0c19LUlIgPSBhc190aWJibGUocmVzdWx0c193ZWlnaHRzX0tSUikKcmVzdWx0c193ZWlnaHRzX0tSUiA9IHJlc3VsdHNfd2VpZ2h0c19LUlIgJT4lIG11dGF0ZShYID0gYXMubnVtZXJpYyhYKSkgJT4lIHBpdm90X2xvbmdlcihjb2xzID0gc3RhcnRzX3dpdGgoIng9IiksIG5hbWVzX3RvID0gIngiLCBuYW1lc19wcmVmaXggPSAieD0iLCB2YWx1ZXNfdG8gPSAid2VpZ2h0IikgJT4lIG11dGF0ZSh4ID0gYXNfZmFjdG9yKHgpKQoKcmVzdWx0c193ZWlnaHRzX0tSUiAlPiUKICBnZ3Bsb3QoYWVzKHggPSBYLCB5ID0gd2VpZ2h0LCBjb2xvciA9IHgpKSsKICBnZW9tX2xpbmUoKSsKICB0aGVtZV9taW5pbWFsKCkKYGBgCiMjIyBWaXN1YWxpemUgUkYKClZpc3VhbGl6ZSBmb3IgS1JSOgoKCmBgYHtyfQpyZXN1bHRzX3dlaWdodHNfUkYgPSBhc190aWJibGUocmVzdWx0c193ZWlnaHRzX1JGKQpyZXN1bHRzX3dlaWdodHNfUkYgPSByZXN1bHRzX3dlaWdodHNfUkYgJT4lIG11dGF0ZShYID0gYXMubnVtZXJpYyhYKSkgJT4lIHBpdm90X2xvbmdlcihjb2xzID0gc3RhcnRzX3dpdGgoIng9IiksIG5hbWVzX3RvID0gIngiLCBuYW1lc19wcmVmaXggPSAieD0iLCB2YWx1ZXNfdG8gPSAid2VpZ2h0IikgJT4lIG11dGF0ZSh4ID0gYXNfZmFjdG9yKHgpKQoKcmVzdWx0c193ZWlnaHRzX1JGICU+JQogIGdncGxvdChhZXMoeCA9IFgsIHkgPSB3ZWlnaHQsIGNvbG9yID0geCkpKwogIGdlb21fbGluZSgpKwogIHRoZW1lX21pbmltYWwoKQpgYGAKIyMjIFZpc3VhbGl6ZSBOVwoKYGBge3J9CnJlc3VsdHNfd2VpZ2h0c19OVyA9IGFzX3RpYmJsZShyZXN1bHRzX3dlaWdodHNfTlcpCnJlc3VsdHNfd2VpZ2h0c19OVyA9IHJlc3VsdHNfd2VpZ2h0c19OVyAlPiUgbXV0YXRlKFggPSBhcy5udW1lcmljKFgpKSAlPiUgcGl2b3RfbG9uZ2VyKGNvbHMgPSBzdGFydHNfd2l0aCgieD0iKSwgbmFtZXNfdG8gPSAieCIsIG5hbWVzX3ByZWZpeCA9ICJ4PSIsIHZhbHVlc190byA9ICJ3ZWlnaHQiKSAlPiUgbXV0YXRlKHggPSBhc19mYWN0b3IoeCkpCgpyZXN1bHRzX3dlaWdodHNfTlcgJT4lCiAgZ2dwbG90KGFlcyh4ID0gWCwgeSA9IHdlaWdodCwgY29sb3IgPSB4KSkrCiAgZ2VvbV9saW5lKCkrCiAgdGhlbWVfbWluaW1hbCgpCmBgYAoKIyMjIFZpc3VhbGl6ZSBYRwoKYGBge3J9CnJlc3VsdHNfd2VpZ2h0c19YRyA9IGFzX3RpYmJsZShyZXN1bHRzX3dlaWdodHNfWEcpCnJlc3VsdHNfd2VpZ2h0c19YRyA9IHJlc3VsdHNfd2VpZ2h0c19YRyAlPiUgbXV0YXRlKFggPSBhcy5udW1lcmljKFgpKSAlPiUgcGl2b3RfbG9uZ2VyKGNvbHMgPSBzdGFydHNfd2l0aCgieD0iKSwgbmFtZXNfdG8gPSAieCIsIG5hbWVzX3ByZWZpeCA9ICJ4PSIsIHZhbHVlc190byA9ICJ3ZWlnaHQiKSAlPiUgbXV0YXRlKHggPSBhc19mYWN0b3IoeCkpCgpyZXN1bHRzX3dlaWdodHNfWEcgJT4lCiAgZ2dwbG90KGFlcyh4ID0gWCwgeSA9IHdlaWdodCwgY29sb3IgPSB4KSkrCiAgZ2VvbV9saW5lKCkrCiAgdGhlbWVfbWluaW1hbCgpCmBgYAoKIyBSZWZlcmVuY2VzCgo8ZGl2IGlkPSJyZWZzIj48L2Rpdj4=